×

Deterministic blow-ups of minimal NFA’s. (English) Zbl 1110.68064

Summary: The paper treats the question whether there always exists a minimal nondeterministic finite automaton of \(n\) states whose equivalent minimal deterministic finite automaton has \( \alpha \) states for any integers \(n\) and \( \alpha \) with \( n \leq \alpha \leq 2^{n}. \) 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 \(n\) and \( \alpha \). However, in order to give an explicit construction of the automata, we increase the input alphabet to exponential sizes. Then we prove that \(2n\) 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.

MSC:

68Q45 Formal languages and automata
68Q19 Descriptive complexity and finite models
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] J.C. Birget , Intersection and union of regular languages and state complexity . Inform. Process. Lett. 43 ( 1992 ) 185 - 190 . Zbl 0763.68048 · Zbl 0763.68048
[2] J.C. Birget , Partial orders on words, minimal elements of regular languages, and state complexity . Theoret. Comput. Sci. 119 ( 1993 ) 267 - 291 . Zbl 0786.68071 · Zbl 0786.68071
[3] P. Berman and A. Lingas , On the complexity of regular languages in terms of finite automata . Technical Report 304, Polish Academy of Sciences ( 1977 ). Zbl 0364.68057 · Zbl 0364.68057
[4] M. Chrobak , Finite automata and unary languages . Theoret. Comput. Sci. 47 ( 1986 ) 149 - 158 . Zbl 0638.68096 · Zbl 0638.68096
[5] M. Chrobak , Errata to: “Finite automata and unary languages ” [Theoret. Comput. Sci. 47 (1986) 149-158]. Theoret. Comput. Sci. 302 ( 2003 ) 497 - 498 . Zbl 0638.68096 · Zbl 0638.68096
[6] I. Glaister and J. Shallit , A lower bound technique for the size of nondeterministic finite automata . Inform. Process. Lett. 59 ( 1996 ) 75 - 77 . Zbl 0900.68313 · Zbl 0900.68313
[7] M. Holzer and M. Kutrib , Nondeterministic descriptional complexity of regular languages . Internat. J. Found. Comput. Sci. 14 ( 2003 ) 1087 - 1102 . Zbl 1101.68657 · Zbl 1101.68657
[8] J. Hromkovič , Communication Complexity and Parallel Computing . Springer-Verlag, Berlin, Heidelberg ( 1997 ). MR 1442518 | Zbl 0873.68098 · Zbl 0873.68098
[9] J. Hromkovič , Descriptional complexity of finite automata: concepts and open problems . J. Autom. Lang. Comb. 7 ( 2002 ) 519 - 531 . Zbl 1094.68576 · Zbl 1094.68576
[10] J. Hromkovič , S. Seibert , J. Karhumäki , H. Klauck and G. Schnitger , Communication complexity method for measuring nondeterminism in finite automata . Inform. Comput. 172 ( 2002 ) 202 - 217 . Zbl 1009.68067 · Zbl 1009.68067
[11] K. Iwama , Y. Kambayashi and K. Takaki , Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs . Theoret. Comput. Sci. 237 ( 2000 ) 485 - 494 . Zbl 0939.68068 · Zbl 0939.68068
[12] K. Iwama , A. Matsuura and M. Paterson , A family of NFAs which need \(2^n-\alpha \) deterministic states . Theoret. Comput. Sci. 301 ( 2003 ) 451 - 462 . Zbl 1022.68067 · Zbl 1022.68067
[13] G. Jirásková , 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 1103.68583 · Zbl 1103.68583
[14] G. Jirásková , 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] O.B. Lupanov , A comparison of two types of finite automata . Problemy Kibernetiki 9 ( 1963 ) 321 - 326 (in Russian).
[16] A.R. Meyer and M.J. Fischer , Economy of description by automata, grammars and formal systems , in Proc. 12th Annual Symposium on Switching and Automata Theory ( 1971 ) 188 - 191 .
[17] F.R. Moore , 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 0229.94033 · Zbl 0229.94033
[18] M. Rabin and D. Scott , Finite automata and their decision problems . IBM Res. Develop. 3 ( 1959 ) 114 - 129 . Zbl 0158.25404 · Zbl 0158.25404
[19] M. Sipser , Lower bounds on the size of sweeping automata . J. Comput. System Sci. 21 ( 1980 ) 195 - 202 . Zbl 0445.68064 · Zbl 0445.68064
[20] M. Sipser , Introduction to the Theory of Computation . PWS Publishing Company, Boston ( 1997 ). · Zbl 1169.68300
[21] S. Yu , 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] S. Yu , A renaissance of automata theory ? Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 72 ( 2000 ) 270 - 272 .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.