Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T14:58:20.251Z Has data issue: false hasContentIssue false
  • English
  • Français

Deterministic blow-ups of minimal NFA's

Published online by Cambridge University Press:  18 October 2006

Galina Jirásková
Galina Jirásková*
Affiliation:
Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia; [email protected]
Get access

Abstract

The paper treats the question whether there always exists a minimal nondeterministic finite automaton of n states whose equivalent minimal deterministic finite automaton has α states for any integers n and α with n ≤ α ≤ 2n. 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 α. 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.

Keywords

Regular languagesdeterministic finite automatanondeterministic finite automatastate complexity.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 3: Word Avoidability Complexity And Morphisms (WACAM) , July 2006 , pp. 485 - 499
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Birget, J.C., Intersection and union of regular languages and state complexity. Inform. Process. Lett. 43 (1992) 185–190. CrossRef
Birget, J.C., Partial orders on words, minimal elements of regular languages, and state complexity. Theoret. Comput. Sci. 119 (1993) 267–291. CrossRef
P. Berman and A. Lingas, On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences (1977).
Chrobak, M., Finite automata and unary languages. Theoret. Comput. Sci. 47 (1986) 149–158. CrossRef
Chrobak, M., Errata to: “Finite automata and unary languages" [ Theoret. Comput. Sci. 47 (1986) 149–158]. Theoret. Comput. Sci. 302 (2003) 497–498. CrossRef
Glaister, I. and Shallit, J., A lower bound technique for the size of nondeterministic finite automata. Inform. Process. Lett. 59 (1996) 75–77. CrossRef
Holzer, M. and Kutrib, M., Nondeterministic descriptional complexity of regular languages. Internat. J. Found. Comput. Sci. 14 (2003) 1087–1102. CrossRef
J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag, Berlin, Heidelberg (1997).
Hromkovič, J., Descriptional complexity of finite automata: concepts and open problems. J. Autom. Lang. Comb. 7 (2002) 519–531.
Hromkovič, J., Seibert, S., Karhumäki, J., Klauck, H. and Schnitger, G., Communication complexity method for measuring nondeterminism in finite automata. Inform. Comput. 172 (2002) 202–217. CrossRef
Iwama, K., Kambayashi, Y. and Takaki, K., Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theoret. Comput. Sci. 237 (2000) 485–494. CrossRef
Iwama, K., Matsuura, A. and Paterson, M., A family of NFAs which need 2 n - α deterministic states. Theoret. Comput. Sci. 301 (2003) 451–462. CrossRef
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.
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.
Lupanov, O.B., A comparison of two types of finite automata. Problemy Kibernetiki 9 (1963) 321–326 (in Russian).
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.
Moore, F.R., 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. CrossRef
Rabin, M. and Scott, D., Finite automata and their decision problems. IBM Res. Develop. 3 (1959) 114–129. CrossRef
Sipser, M., Lower bounds on the size of sweeping automata. J. Comput. System Sci. 21 (1980) 195–202. CrossRef
M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997).
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.
Yu, S., A renaissance of automata theory? Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 72 (2000) 270–272.