×

zbMATH — the first resource for mathematics

Magic numbers in the state hierarchy of finite automata. (English) Zbl 1130.68069
Summary: A number \(d\) is magic for \(n\), if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly \(n\) states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly \(d\) states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by \(n\)-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers. Actually, most of the numbers is magic in the unary case. As an additional bonus, we also get a new universal lower bound for the conversion of unary \(d\)-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below \(\log ^{2} d\), not even in the best case.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alt, H., Lower bounds on space complexity for context-free recognition, Acta inform., 12, 33-61, (1979) · Zbl 0389.68043
[2] Alt, H.; Geffert, V.; Mehlhorn, K., A lower bound for the nondeterministic space complexity of context-free recognition, Inform. process. lett., 42, 25-27, (1992) · Zbl 0780.68081
[3] Bertoni, A.; Mereghetti, C.; Pighizzini, G., An optimal lower bound for nonregular languages, Inform. process. lett., 50, 289-292, (1994), (Corrigendum: 1994, ibid. 52, 339.) · Zbl 0810.68089
[4] Chrobak, M., Finite automata and unary languages, Theor. comput. sci., 47, 149-158, (1986), (Corrigendum: 2003, ibid. 302, 497-498.) · Zbl 0638.68096
[5] Geffert, V., Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. comput., 20, 484-498, (1991) · Zbl 0762.68022
[6] Geffert, V., Space hierarchy theorem revised, Theor. comput. sci., 295, 171-187, (2003) · Zbl 1038.68053
[7] V. Geffert, (Non)determinism and the size of one-way finite automata, in: Proc. Descr. Compl. Formal Systems, IFIP & University Milano, 2005, pp. 23-37.
[8] Geffert, V.; Mereghetti, C.; Pighizzini, G., Converting two-way nondeterministic unary automata into simpler automata, Theor. comput. sci., 295, 189-203, (2003) · Zbl 1045.68080
[9] Hardy, G.; Wright, E., An introduction to the theory of numbers, (1979), Oxford University Press · Zbl 0423.10001
[10] Hopcroft, J.; Motwani, R.; Ullman, J., Introduction to automata theory, languages, and computation, (2001), Addison-Wesley · Zbl 0980.68066
[11] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley · Zbl 0196.01701
[12] Iwama, K.; Kambayashi, Y.; Takaki, K., Tight bounds on the number of states of DFA’s that are equivalent to n-state NFA’s, Theor. comput. sci., 237, 485-494, (2000) · Zbl 0939.68068
[13] Iwama, K.; Matsuura, A.; Paterson, M., A family of NFA’s which need 2^n−α deterministic states, Theor. comput. sci., 301, 451-462, (2003) · Zbl 1022.68067
[14] Jirásková, G., Note on minimal finite automata, (), 421-431 · Zbl 0999.68104
[15] Ljubič, Ju.I., Ocenki dlja optimaĺnoj determinizacii nedeterminirovannyh avtonomnyh avtomatov, Sibirsk. mat. zh., V/2, 337-355, (1964), (in Russian)
[16] Lupanov, O.B., Uber den vergleich zweier typen endlicher quellen, Probleme der kybernetik, 6, 329-335, (1966), (Akademie-Verlag, Berlin, in German) · Zbl 0168.25902
[17] Mereghetti, C.; Pighizzini, G., Optimal simulations between unary automata, SIAM J. comput., 30, 1976-1992, (2001) · Zbl 0980.68048
[18] Moore, F., On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE trans. comput., C-20, 1211-1214, (1971) · Zbl 0229.94033
[19] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. res. develop., 3, 114-125, (1959) · Zbl 0158.25404
[20] W. Sakoda, M. Sipser, Nondeterminism and the size of two-way finite automata, in Proc. ACM Symp. Theory of Comput., 1978, pp. 275-286. · Zbl 1282.68160
[21] Salomaa, A.; Wood, D.; Yu, S., On the state complexity of reversals of regular languages, Theor. comput. sci., 320, 315-329, (2004) · Zbl 1068.68078
[22] Szalay, M., On the maximal order in S_n and sn∗, Acta arith., 37, 321-331, (1980) · Zbl 0443.10029
[23] Yau, S.Y., Number theory for computing, (2002), Springer-Verlag
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.