The paper treats the question whether there always exists a minimal nondeterministic finite automaton of states whose equivalent minimal deterministic finite automaton has states for any integers and with Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of and . However, in order to give an explicit construction of the automata, we increase the input alphabet to exponential sizes. Then we prove that letters would be sufficient but we describe the related automata only implicitly. In the last section, we investigate the above question for automata over binary and unary alphabets.
Mots-clés : regular languages, deterministic finite automata, nondeterministic finite automata, state complexity
@article{ITA_2006__40_3_485_0, author = {Jir\'askov\'a, Galina}, title = {Deterministic blow-ups of minimal {NFA's}}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {485--499}, publisher = {EDP-Sciences}, volume = {40}, number = {3}, year = {2006}, doi = {10.1051/ita:2006032}, zbl = {1110.68064}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2006032/} }
TY - JOUR AU - Jirásková, Galina TI - Deterministic blow-ups of minimal NFA's JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 485 EP - 499 VL - 40 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2006032/ DO - 10.1051/ita:2006032 LA - en ID - ITA_2006__40_3_485_0 ER -
%0 Journal Article %A Jirásková, Galina %T Deterministic blow-ups of minimal NFA's %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 485-499 %V 40 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2006032/ %R 10.1051/ita:2006032 %G en %F ITA_2006__40_3_485_0
Jirásková, Galina. Deterministic blow-ups of minimal NFA's. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 485-499. doi : 10.1051/ita:2006032. http://archive.numdam.org/articles/10.1051/ita:2006032/
[1] Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43 (1992) 185-190. | Zbl
,[2] Partial orders on words, minimal elements of regular languages, and state complexity. Theoret. Comput. Sci. 119 (1993) 267-291. | Zbl
,[3] On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences (1977). | Zbl
and ,[4] Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-158. | Zbl
,[5] Errata to: “Finite automata and unary languages ” [Theoret. Comput. Sci. 47 (1986) 149-158]. Theoret. Comput. Sci. 302 (2003) 497-498. | Zbl
,[6] A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59 (1996) 75-77. | Zbl
and ,[7] Nondeterministic descriptional complexity of regular languages. Internat. J. Found. Comput. Sci. 14 (2003) 1087-1102. | Zbl
and ,[8] Communication Complexity and Parallel Computing. Springer-Verlag, Berlin, Heidelberg (1997). | MR | Zbl
,[9] Descriptional complexity of finite automata: concepts and open problems. J. Autom. Lang. Comb. 7 (2002) 519-531. | Zbl
,[10] Communication complexity method for measuring nondeterminism in finite automata. Inform. Comput. 172 (2002) 202-217. | Zbl
, , , and ,[11] Tight bounds on the number of states of DFAs that are equivalent to -state NFAs. Theoret. Comput. Sci. 237 (2000) 485-494. | Zbl
, and ,[12] A family of NFAs which need deterministic states. Theoret. Comput. Sci. 301 (2003) 451-462. | Zbl
, and ,[13] Note on minimal automata and uniform communication protocols, in Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back, edited by C. Martin-Vide, V. Mitrana, Taylor and Francis, London (2003) 163-170. | Zbl
,[14] State complexity of some operations on regular languages, in Proc. 5th Workshop Descriptional Complexity of Formal Systems, edited by E. Csuhaj-Varjú, C. Kintala, D. Wotschke, Gy. Vaszil, MTA SZTAKI, Budapest (2003) 114-125.
,[15] A comparison of two types of finite automata. Problemy Kibernetiki 9 (1963) 321-326 (in Russian).
,[16] Economy of description by automata, grammars and formal systems, in Proc. 12th Annual Symposium on Switching and Automata Theory (1971) 188-191.
and ,[17] On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20 (1971) 1211-1214. | Zbl
,[18] Finite automata and their decision problems. IBM Res. Develop. 3 (1959) 114-129. | Zbl
and ,[19] Lower bounds on the size of sweeping automata. J. Comput. System Sci. 21 (1980) 195-202. | Zbl
,[20] Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997).
,[21] Chapter 2: Regular languages, in Handbook of Formal Languages - Vol. I, edited by G. Rozenberg, A. Salomaa, Springer-Verlag, Berlin, New York (1997) 41-110.
,[22] A renaissance of automata theory? Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 72 (2000) 270-272.
,Cité par Sources :