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 $\epsilon$-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\left(n\right)$ states, $O\left(nlogn\right)$ $\epsilon$-transitions, and $O\left(n\right)$ alphabet-transitions. We also show how to easily transform these $2$-realtime machines into $1$-realtime automata, still with only $O\left(nlogn\right)$ edges. These results contrast with the known lower bound $\Omega \left(n{\left(logn\right)}^{2}/loglogn\right)$, holding for $0$-realtime automata, i.e., for automata with no $\epsilon$-transitions.

DOI : https://doi.org/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
DA  - 2006///
SP  - 611
EP  - 629
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006036/
UR  - https://zbmath.org/?q=an%3A1110.68063
UR  - https://doi.org/10.1051/ita:2006036
DO  - 10.1051/ita:2006036
LA  - en
ID  - ITA_2006__40_4_611_0
ER  - 
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 0329.94024

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

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

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

[5] J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small $\epsilon$-free nondeterministic automata, in Proc. Symp. Theoret. Aspects Comput. Sci. Lect. Notes Comput. Sci. 1200 (1997) 55-66. | Zbl 1014.68093

[6] J. Hromkovič, S. Seibert and T. Wilke, Translating regular expressions into small $\epsilon$-free nondeterministic finite automata. J. Comput. Syst. Sci. 62 (2001) 565-88. | Zbl 1014.68093

[7] Yu. Lifshits, A lower bound on the size of $\epsilon$-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 960693 | Zbl 0651.68007

Cité par Sources :