Conversion of regular expressions into realtime automata

Viliam Geffert; L'ubomíra Ištoňová

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 4, page 611-629
  • ISSN: 0988-3754

Abstract

top
We consider conversions of regular expressions into k-realtime finite state automata, i.e., automata in which the number of consecutive uses of ε-transitions, along any computation path, is bounded by a fixed constant k. For 2-realtime automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only O(n) states, O(nlogn) ε-transitions, and O(n) alphabet-transitions. We also show how to easily transform these 2-realtime machines into 1-realtime automata, still with only O(nlogn) edges. These results contrast with the known lower bound Ω(n(logn)2 / loglogn), holding for 0-realtime automata, i.e., for automata with no ε-transitions.

How to cite

top

Geffert, Viliam, and Ištoňová, L'ubomíra. "Conversion of regular expressions into realtime automata." RAIRO - Theoretical Informatics and Applications 40.4 (2006): 611-629. <http://eudml.org/doc/249737>.

@article{Geffert2006,
abstract = { We consider conversions of regular expressions into k-realtime finite state automata, i.e., automata in which the number of consecutive uses of ε-transitions, along any computation path, is bounded by a fixed constant k. For 2-realtime automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only O(n) states, O(nlogn) ε-transitions, and O(n) alphabet-transitions. We also show how to easily transform these 2-realtime machines into 1-realtime automata, still with only O(nlogn) edges. These results contrast with the known lower bound Ω(n(logn)2 / loglogn), holding for 0-realtime automata, i.e., for automata with no ε-transitions. },
author = {Geffert, Viliam, Ištoňová, L'ubomíra},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Descriptional complexity; finite-state automata; regular expressions.; descriptional complexity; regular expressions},
language = {eng},
month = {11},
number = {4},
pages = {611-629},
publisher = {EDP Sciences},
title = {Conversion of regular expressions into realtime automata},
url = {http://eudml.org/doc/249737},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Geffert, Viliam
AU - Ištoňová, L'ubomíra
TI - Conversion of regular expressions into realtime automata
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/11//
PB - EDP Sciences
VL - 40
IS - 4
SP - 611
EP - 629
AB - We consider conversions of regular expressions into k-realtime finite state automata, i.e., automata in which the number of consecutive uses of ε-transitions, along any computation path, is bounded by a fixed constant k. For 2-realtime automata, i.e., for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only O(n) states, O(nlogn) ε-transitions, and O(n) alphabet-transitions. We also show how to easily transform these 2-realtime machines into 1-realtime automata, still with only O(nlogn) edges. These results contrast with the known lower bound Ω(n(logn)2 / loglogn), holding for 0-realtime automata, i.e., for automata with no ε-transitions.
LA - eng
KW - Descriptional complexity; finite-state automata; regular expressions.; descriptional complexity; regular expressions
UR - http://eudml.org/doc/249737
ER -

References

top
  1. A. Ehrenfeucht and P. Zieger, Complexity measures for regular expressions. J. Comput. Syst. Sci.12 (1976) 134–46.  
  2. V. Geffert, Translation of binary regular expressions into nondeterministic ε-free automata with O(nlogn) transitions. J. Comput. Syst. Sci.67 (2003) 451–72.  
  3. S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975).  
  4. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979).  
  5. J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic automata, in Proc. Symp. Theoret. Aspects Comput. Sci.Lect. Notes Comput. Sci.1200 (1997) 55–66.  
  6. J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small ε-free nondeterministic finite automata. J. Comput. Syst. Sci.62 (2001) 565–88.  
  7. Yu. Lifshits, A lower bound on the size of ε-free NFA corresponding to a regular expression. Inform. Process. Lett.85 (2003) 293–99.  
  8. S. Sippu and E. Soisalon-Soininen, Parsing Theory, Vol. I: Languages and Parsing. EATCS Monographs in Theoret. Comput. Sci.15 (1988).  

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.