Special Issue – Developments in Language Theory (DLT 2010)No Access

COMPLEXITY IN UNION-FREE REGULAR LANGUAGES

Mathematical Institute, Slovak Academy of Sciences Grešákova 6, 040 01 Košice, Slovakia

Research supported by VEGA grant 2/0183/11, and by the Slovak Research and Development Agency under contract APVV-0035-10 "Algorithms, Automata, and Discrete Data Structures."

Search for more papers by this author

and

TOMÁŠ MASOPUST

CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands

Mathematical Institute, Czech Academy of Sciences, Žižkova 22, 616 62 Brno, Czech Republic

Research supported by the CAS, Institutional Research Plan no. AV0Z10190503.

Search for more papers by this author

https://doi.org/10.1142/S0129054111008933Cited by:24 (Source: Crossref)

Abstract

We continue the investigation of union-free regular languages that are described by regular expressions without the union operation. We also define deterministic union-free languages as languages accepted by one-cycle-free-path deterministic finite automata, and show that they are properly included in the class of union-free languages. We prove that (deterministic) union-freeness of languages does not accelerate regular operations, except for the reversal in the nondeterministic case.

This paper has been presented at the 14th Conference on Developments in Language Theory (DLT 2010) held in London, Ontario, Canada on August 17-20, 2010.

Keywords:

References

S. Afonin and D. Golomazov, Minimal union-free decompositions of regular languages, Proc. of LATA 20095457, LNCS (Springer, 2009) pp. 83–92. Google Scholar
A. V. Aho, J. D. Ullman and M. Yannakakis, On notions of information transfer in VLSI circuits, Proc. of STOC 1983 (1983) pp. 133–139. Google Scholar
J.-C. Birget, Inform. Process. Lett. 43, 185 (1992), DOI: 10.1016/0020-0190(92)90198-5. Crossref, Web of Science, Google Scholar
J.-C. Birget, Theoret. Comput. Sci. 119, 267 (1993), http://clam.rutgers.edu/~birget/poWordsERR.ps DOI: 10.1016/0304-3975(93)90160-U. Crossref, Web of Science, Google Scholar
J. Brzozowski. Regular expression techniques for sequential circuits. PhD thesis, Department of Electrical Engineering, Princeton University, Princeton, NJ, June 1962 . Google Scholar
C. Câmpeanu, K. Salomaa and S. Yu, J. Autom. Lang. Comb. 7(3), 303 (2002). Google Scholar
S. Crvenković, I. Dolinka and Zoltán Ésik, Inform. and Comput. 164(1), 152 (2001). Crossref, Web of Science, Google Scholar
M. Domaratzki, D. Kisman and J. Shallit, J. Autom. Lang. Comb. 7(4), 469 (2002). Google Scholar
M. Domaratzki and A. Okhotin, Theoret. Comput. Sci. 410(24-25), 2377 (2009), DOI: 10.1016/j.tcs.2009.02.025. Crossref, Web of Science, Google Scholar
I. Glaister and J. Shallit, Inform. Process. Lett. 59, 75 (1996), DOI: 10.1016/0020-0190(96)00095-6. Crossref, Web of Science, Google Scholar
Y.-S. Han and K. Salomaa, Theoret. Comput. Sci. 410(27-29), 2537 (2009), DOI: 10.1016/j.tcs.2008.12.054. Crossref, Web of Science, Google Scholar
M. Holzer and M. Kutrib, Inform. and Comput. 209(3), 456 (2011), DOI: 10.1016/j.ic.2010.11.013. Crossref, Web of Science, Google Scholar
J. Hromkovič , Communication complexity and parallel computing ( Springer , Heidelberg , 1997 ) . Crossref, Google Scholar
J. Jirásek, G. Jirásková and A. Szabari, Int. J. Found. Comput. Sci. 16(3), 511 (2005). Link, Web of Science, Google Scholar
G. Jirásková, Theoret. Comput. Sci. 330, 287 (2005), DOI: 10.1016/j.tcs.2004.04.011. Crossref, Web of Science, Google Scholar
G. Jirásková and A. Okhotin, Theor. Inform. Appl. 42(2), 335 (2008), DOI: 10.1051/ita:2007038. Crossref, Web of Science, Google Scholar
G. Jirásková and A. Okhotin, Nondeterministic state complexity of positional addition, Proc. of DCFS 20093, EPTCS (2009) pp. 151–161. Google Scholar
M. Kutrib and M. Holzer, Int. J. Found. Comput. Sci. 14(6), 1087 (2003). Google Scholar
E. Leiss, Theoret. Comput. Sci. 13, 323 (1981). Crossref, Web of Science, Google Scholar
O. B. Lupanov, Probl. Kybernetik 6, 328 (1966). Web of Science, Google Scholar
A. N. Maslov, Soviet Math. Dokl. 11(5), 1373 (1970). Google Scholar
R. McNaughton and S. Papert , Counter-Free Automata ( The MIT Press , 1971 ) . Google Scholar
A. R. Meyer and M. J. Fischer, Economy of description by automata, grammars, and formal systems, Proc. of FOCS 1971 (IEEE, 1971) pp. 188–191. Google Scholar
B. G. Mirkin, Kibernetika 2(1), 7 (1966). Google Scholar
F. R. Moore, IEEE Trans. Comput. 20(10), 1211 (1971). Web of Science, Google Scholar
B. Nagy, Publ. Math. Debrecen 68(1-2), 183 (2006). Crossref, Web of Science, Google Scholar
B. Nagy, On union-complexity of regular languages, Proc. of CINTI 2010 (IEEE, 2010) pp. 177–182. Google Scholar
N. Rampersad, Inform. Process. Lett. 98(6), 231 (2006). Crossref, Web of Science, Google Scholar
A. Salomaa, D. Wood and S. Yu, Theoret. Comput. Sci. 320, 315 (2004). Crossref, Web of Science, Google Scholar
M. Sipser , Introduction to the theory of computation ( PWS Publishing Company , Boston , 1997 ) . Google Scholar
S. Yu, Handbook of Formal Languages I (Springer, Heidelberg, 1997) pp. 41–110. Crossref, Google Scholar
S. Yu, Q. Zhuang and K. Salomaa, Theoret. Comput. Sci. 125(2), 315 (1994), DOI: 10.1016/0304-3975(92)00011-F. Crossref, Web of Science, Google Scholar