An upper bound for transforming self-verifying automata into deterministic ones. (English) Zbl 1130.68067

Assent, Ira; Seibert, Sebastian

Theor. Inform. Appl. 41, No. 3, 261-265 (2007).

Summary: 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(\frac{2^n}{\sqrt{n}})\).

MSC:

68Q45	Formal languages and automata
68Q19	Descriptive complexity and finite models

Keywords:

self-verifying nondeterministic automata; descriptional complexity; power set construction

References:

[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 · 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 · 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 · Zbl 0229.94033