More Web Proxy on the site http://driver.im/

Article

Magic numbers in the state hierarchy of finite automata

Author:

Viliam GeffertAuthors Info & Claims

MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer Science

Pages 412 - 423

https://doi.org/10.1007/11821069_36

Published: 28 August 2006 Publication History

Abstract

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, but for which 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 [7].

As an additional bonus, we get a 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²d, not even in the best case.

References

[1]

Bertoni, A., Mereghetti, C., Pighizzini, G.: An optimal lower bound for nonregular languages. Inform. Process. Lett. 50 (1994) 289-92. (Corrigendum: ibid. 52 (1994) p. 339).

Digital Library

[2]

Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149-58. (Corrigendum: ibid. 302 (2003) 497-98).

Digital Library

[3]

Geffert, V.: (Non)determinism and the size of one-way finite automata. In Proc. Descr. Compl. Formal Syst. (2005) 23-37. (IFIP & Univ. Milano).

[4]

Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295 (2003) 189-203.

Digital Library

[5]

Hardy, G., Wright, E.: An Introduction to the Theory of Numbers. Oxford University Press, 5th edit., 1979.

[6]

Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.

Digital Library

[7]

Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFA's that are equivalent to n-state NFA's. Theoret. Comput. Sci. 237 (2000) 485-94.

Digital Library

[8]

Iwama, K., Matsuura, A., Paterson, M.: A family of NFA's which need 2ⁿ - α deterministic states. Theoret. Comput. Sci. 301 (2003) 451-62.

Digital Library

[9]

Jirásková, G.: Note on minimal finite automata. In Proc. Math. Found. Comput. Sci., Lect. Notes Comput. Sci. 2136 (2001) 421-31.

Digital Library

[10]

Lupanov, O.B.: Uber den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6 (1966) 329-35. (Akademie-Verlag, Berlin, in German).

[11]

Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30 (2001) 1976-92.

Digital Library

[12]

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 (1971) 1211-14.

Digital Library

[13]

Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959) 114-25.

Digital Library

[14]

Sakoda, W., Sipser, M.: Nondeterminism and the size of two-way finite automata. In Proc. ACM Symp. Theory of Comput. (1978) 275-86.

Digital Library

[15]

Szalay, M.: On the maximal order in Sn and S_n ^*. Acta Arith. 37 (1980) 321-31.

Cited By

Jirásková G(2008)On the State Complexity of Complements, Stars, and Reversals of Regular LanguagesProceedings of the 12th international conference on Developments in Language Theory10.1007/978-3-540-85780-8_34(431-442)Online publication date: 16-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85780-8_34
Jirásek JJirásková GSzabari A(2007)Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabetProceedings of the 11th international conference on Developments in language theory10.5555/1770310.1770337(254-265)Online publication date: 3-Jul-2007
https://dl.acm.org/doi/10.5555/1770310.1770337

Recommendations

Magic numbers in the state hierarchy of finite automata

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 ...
State hierarchy for one-way finite automata

Quite recently, it has been shown that, for each n, and each d between n and 2ⁿ, there exists a regular language for which each optimal nondeterministic one-way finite state automaton (nfa) uses exactly n states, but its optimal deterministic ...
An alternating hierarchy for finite automata

We study the polynomial state complexity classes 2@S"k and 2@P"k, that is, the hierarchy of problems that can be solved with a polynomial number of states by two-way alternating finite automata (2Afas) making at most k-1 alternations between existential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer Science

August 2006

813 pages

ISBN:3540377913

Editors:
Rastislav Královič
Department of Computer Science, Comenius University, Mlynská dolina, Bratislava, Slovakia
,
Paweł Urzyczyn
Institute of Informatics, University of Warsaw, Bratislava, Poland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 28 August 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jirásková G(2008)On the State Complexity of Complements, Stars, and Reversals of Regular LanguagesProceedings of the 12th international conference on Developments in Language Theory10.1007/978-3-540-85780-8_34(431-442)Online publication date: 16-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85780-8_34
Jirásek JJirásková GSzabari A(2007)Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabetProceedings of the 11th international conference on Developments in language theory10.5555/1770310.1770337(254-265)Online publication date: 3-Jul-2007
https://dl.acm.org/doi/10.5555/1770310.1770337

View Options

View options

Figures

Tables

Media

View Table of Conten