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

Ira Assent; Sebastian Seibert

RAIRO - Theoretical Informatics and Applications (2007)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.