Conversion of regular expressions into realtime automata

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

doi:10.1051/ita:2006036

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 611-629.

Résumé

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 (n log n)$ $ε$ -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 (n log n)$ edges. These results contrast with the known lower bound $Ω (n {(log n)}^{2} / log log n)$ , holding for $0$ -realtime automata, i.e., for automata with no $ε$ -transitions.

Zbl

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/

Bibliographie
Cité par

[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 (n log n)$ 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 :