An upper bound for transforming self-verifying automata into deterministic ones
Assent, Ira ; Seibert, Sebastian
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007), p. 261-265 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from 2 n to O(2 n n).

Publié le : 2007-01-01
DOI : https://doi.org/10.1051/ita:2007017
Classification:  68Q10,  68Q19 
@article{ITA_2007__41_3_261_0,
     author = {Assent, Ira and Seibert, Sebastian},
     title = {An upper bound for transforming self-verifying automata into deterministic ones},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {41},
     year = {2007},
     pages = {261-265},
     doi = {10.1051/ita:2007017},
     mrnumber = {2354357},
     zbl = {1130.68067},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2007__41_3_261_0}
}

Assent, Ira; Seibert, Sebastian. An upper bound for transforming self-verifying automata into deterministic ones. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) pp. 261-265. doi : 10.1051/ita:2007017. http://gdmltest.u-ga.fr/item/ITA_2007__41_3_261_0/

[1] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA (1979). | MR 645539 | Zbl 0426.68001

[2] J. Hromkovič and G. Schnitger, On the Power of Las Vegas for One-way Communication Complexity, OBDDS, Finite Automata. Inform. Comput. 169 (2001) 284-296. | Zbl 1007.68065

[3] O.B. Lupanov, A comparision of two types of finite automata. Problemy Kibernetiki 9 (1963) 321-326 (Russian).

[4] A.R. Meyer and M.J. Fischer, Economy of Description by Automata, Grammars, and Formal Systems, in Proc. IEEE 12th Ann. Symp. on Switching and Automata Theory 1971, 188-191.

[5] 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