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\left(\frac{{2}^{n}}{\sqrt{n}}\right).$

DOI : https://doi.org/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},
zbl = {1130.68067},
mrnumber = {2354357},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita:2007017/}
}
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://archive.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 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