An upper bound for transforming self-verifying automata into deterministic ones
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 41 (2007) no. 3, pp. 261-265.

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).

DOI : 10.1051/ita:2007017
Classification : 68Q10, 68Q19
Mots-clés : self-verifying nondeterministic automata, descriptional complexity, power set construction 
@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},
     pages = {261--265},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {3},
     year = {2007},
     doi = {10.1051/ita:2007017},
     mrnumber = {2354357},
     zbl = {1130.68067},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2007017/}
}
TY  - JOUR
AU  - Assent, Ira
AU  - Seibert, Sebastian
TI  - An upper bound for transforming self-verifying automata into deterministic ones
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2007
SP  - 261
EP  - 265
VL  - 41
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2007017/
DO  - 10.1051/ita:2007017
LA  - en
ID  - ITA_2007__41_3_261_0
ER  - 
%0 Journal Article
%A Assent, Ira
%A Seibert, Sebastian
%T An upper bound for transforming self-verifying automata into deterministic ones
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2007
%P 261-265
%V 41
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2007017/
%R 10.1051/ita:2007017
%G en
%F 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) no. 3, pp. 261-265. doi : 10.1051/ita:2007017. http://www.numdam.org/articles/10.1051/ita:2007017/

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

[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

[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

Cité par Sources :