Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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≤α≤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 α. 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.

DOI : 10.1051/ita:2006032
Classification : 68Q45, 68Q19
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :