Mirror Images and Schemes for the Maximal Complexity of Nondeterminism

• Autorzy: Salomaa A.
• Języki publikacji: EN

Abstrakty

EN

We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.

Słowa kluczowe

EN

state complexity; finite automaton; scheme of automata; nondeterminism; construction; mirror image; reversal

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 237--249
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Salomaa A.

• Turku Centre for Computer Science Joukahaisenkatu 3–5 B, 20520 Turku, Finland,

Bibliografia

• [1] Esik, Z, Gao, Y, Liu, G and Yu, S., Estimation of State Complexity of Combined Operations. Theoretical Computer Science 410 (35) (2009), 3272-3280.
• [2] Gao, Y, Salomaa, K. and Yu, S., State complexity of catenation and reversal combined with star. Descriptional Complexity of Formal Systems (DCFS 2006) 153-164.
• [3] Jirásková, G. and Masopust, T., Complexity in union-free regular languages. Springer Lecture Notes in Computer Science 6224 (2010) 255-266.
• [4] Leiss, E., Succinct representation of regular languages by boolean automata. Theoretical Computer Science 13 (1981) 323-330.
• [5] Lupanov, O.B., O sravnenii dvukh tipov konechnykh istochnikov. Problemy Kibernetiki 9 (1963) 321-326
• [6] Salomaa, A., Composition sequences for functions over a finite domain. Theoretical Computer Science 292 (2003) 263-281.
• [7] Salomaa, A., Salomaa, K. and Yu, S., State Complexity of Combined Operations. Theoretical Computer Science, 383 (2007) 140-152.
• [8] Salomaa, A., Salomaa, K. and Yu, S., Undecidability of the state complexity of composed regular operations. Proceedings LATA-2011 (2011).
• [9] Salomaa, A., Wood, D. and Yu, S., On the state complexity of reversals of regular languages. Theoretical Computer Science 320 (2004) 315-329.
• [10] Šebej, J., Reversal of regular languages and state complexity.Manuscript (2010) submitted for publication.
• [11] Yu, S., Zhuang, Q. and Salomaa, K., The state complexities of some basic operations on regular languages. Theoretical Computer Science 125 (1994) 315-328.
• [12] Yu, S., Regular Languages, in: Handbook of Formal Languages, Vol. I, G. Rozenberg and A. Salomaa eds., Springer Verlag, 1997, pp. 41-110.