Mirror Images and Schemes for the Maximal Complexity of Nondeterminism

Issue title: Words, Graphs, Automata, and Languages; Special Issue Honoring the 60th Birthday of Professor Tero Harju

Article type: Research Article

Authors: Salomaa, Arto

Affiliations: Turku Centre for Computer Science, Joukahaisenkatu 3–5 B, 20520 Turku, Finland, asalomaa@utu.fi

Note: [] Address for correspondence: Turku Centre for Computer Science, Joukahaisenkatu 3–5 B, 20520 Turku, Finland

Abstract: 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.

Keywords: state complexity, finite automaton, scheme of automata, nondeterminism, subset construction, mirror image, reversal

DOI: 10.3233/FI-2012-681

Journal: Fundamenta Informaticae, vol. 116, no. 1-4, pp. 237-249, 2012