×

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

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
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML Link

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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.