Conversion of regular expressions into realtime automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 611-629.

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.

DOI : 10.1051/ita:2006036
Classification : 68Q45
Mots clés : descriptional complexity, finite-state automata, regular expressions
@article{ITA_2006__40_4_611_0,
     author = {Geffert, Viliam and I\v{s}to\v{n}ov\'a, L'ubom{\'\i}ra},
     title = {Conversion of regular expressions into realtime automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {611--629},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006036},
     zbl = {1110.68063},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006036/}
}
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 - Informatique Théorique et Applications
PY  - 2006
SP  - 611
EP  - 629
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006036/
DO  - 10.1051/ita:2006036
LA  - en
ID  - ITA_2006__40_4_611_0
ER  - 
%0 Journal Article
%A Geffert, Viliam
%A Ištoňová, L'ubomíra
%T Conversion of regular expressions into realtime automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 611-629
%V 40
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2006036/
%R 10.1051/ita:2006036
%G en
%F ITA_2006__40_4_611_0
Geffert, Viliam; Ištoňová, L'ubomíra. Conversion of regular expressions into realtime automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 611-629. doi : 10.1051/ita:2006036. http://www.numdam.org/articles/10.1051/ita:2006036/

[1] A. Ehrenfeucht and P. Zieger, Complexity measures for regular expressions. J. Comput. Syst. Sci. 12 (1976) 134-46. | Zbl

[2] V. Geffert, Translation of binary regular expressions into nondeterministic ε-free automata with O(nlogn) transitions. J. Comput. Syst. Sci. 67 (2003) 451-72. | Zbl

[3] S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland (1975). | MR | Zbl

[4] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (1979). | MR | Zbl

[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. | Zbl

[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. | Zbl

[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). | MR | Zbl

Cité par Sources :