# An upper bound for transforming self-verifying automata into deterministic ones

RAIRO - Theoretical Informatics and Applications (2007)

- Volume: 41, Issue: 3, page 261-265
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAssent, Ira, and Seibert, Sebastian. "An upper bound for transforming self-verifying automata into deterministic ones." RAIRO - Theoretical Informatics and Applications 41.3 (2007): 261-265. <http://eudml.org/doc/250018>.

@article{Assent2007,

abstract = {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\}\}).$},

author = {Assent, Ira, Seibert, Sebastian},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Self-verifying nondeterministic automata; descriptional
complexity; power set construction; self-verifying nondeterministic automata; descriptional complexity},

language = {eng},

month = {9},

number = {3},

pages = {261-265},

publisher = {EDP Sciences},

title = {An upper bound for transforming self-verifying automata into deterministic ones},

url = {http://eudml.org/doc/250018},

volume = {41},

year = {2007},

}

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

DA - 2007/9//

PB - EDP Sciences

VL - 41

IS - 3

SP - 261

EP - 265

AB - 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}}).$

LA - eng

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

UR - http://eudml.org/doc/250018

ER -

## References

top- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA (1979).
- 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.
- O.B. Lupanov, A comparision of two types of finite automata. Problemy Kibernetiki9 (1963) 321–326 (Russian).
- 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.
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.