Computing ε-free NFA from regular expressions in O(nlog 2 (n)) time
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 4, pp. 257-277. 
@article{ITA_2000__34_4_257_0,
     author = {Hagenah, Christian and Muscholl, Anca},
     title = {Computing $\varepsilon $-free {NFA} from regular expressions in $O(n \log ^2 (n))$ time},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {257--277},
     publisher = {EDP-Sciences},
     volume = {34},
     number = {4},
     year = {2000},
     mrnumber = {1809860},
     zbl = {0971.68091},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2000__34_4_257_0/}
}
TY  - JOUR
AU  - Hagenah, Christian
AU  - Muscholl, Anca
TI  - Computing $\varepsilon $-free NFA from regular expressions in $O(n \log ^2 (n))$ time
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 257
EP  - 277
VL  - 34
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2000__34_4_257_0/
LA  - en
ID  - ITA_2000__34_4_257_0
ER  - 
%0 Journal Article
%A Hagenah, Christian
%A Muscholl, Anca
%T Computing $\varepsilon $-free NFA from regular expressions in $O(n \log ^2 (n))$ time
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 257-277
%V 34
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_2000__34_4_257_0/
%G en
%F ITA_2000__34_4_257_0
Hagenah, Christian; Muscholl, Anca. Computing $\varepsilon $-free NFA from regular expressions in $O(n \log ^2 (n))$ time. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 4, pp. 257-277. http://www.numdam.org/item/ITA_2000__34_4_257_0/

[1] G. Berry and R. Sethi, From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. | MR | Zbl

[2] J. Berstel and J.-É. Pin, Local languages and the Berry-Sethi algorithm. Theoret. Comput. Sci. 155 (1996) 439-446. | MR | Zbl

[3] A. Brüggemann-Klein, Regular expressions into finite automata. Theoret. Comput. Sci. 120 (1993) 197-213. | MR | Zbl

[4] A. Ehrenfeucht and P. Zeiger, Complexity measures for regular expressions. J. Comput. System Sci. 12 (1976) 134-146. | MR | Zbl

[5] A. Gibbons and W. Rytter, Efficient parallel algorithms. Cambridge University Press (1989). | MR | Zbl

[6] V. M. Glushkov, The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53. | MR | Zbl

[7] Ch. Hagenah and A. Muscholl, Computing ε-free NFA from regular expressions in O(n log2(n)) time, in Proc. of the 23rd Symposium on Mathematical Foundations of Computer Science (MFCS'98, Brno, Czech Rep.), edited by L. Brim et al Springer, Lecture Notes in Comput. Sci. 1450 (1998) 277-285. | MR | Zbl

[8] J. Hromkovič, S. Seibert and Th. Wilke, Translating regular expressions into small ε-free nondeterministic finite automata, in Proc. of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS'97, Lübeck, Germany), edited by R. Reischuk et al. Springer, Lecture Notes in Comput. Sci. 1200 (1997) 55-66. | MR

[9] J. Jájá, An introduction to parallel algorithms. Addison-Wesley, Reading, MA (1992). | Zbl

[10] R. Mcnaughton and H. Yamada, Regular expressions and state graphs for automata. IRE Trans. Electron. Comput. EC-9 (1960) 39-47. | Zbl

[11] J.-L. Ponty, D. Ziadi and J.-M. Champarnaud, A new quadratic algorithm to convert a regular expression into an automaton, in Proc. of the First International Workshop on Implementing Automata, WIA'96, edited by D. Raymond et al. Springer, Lecture Notes in Comput. Sci. 1260 (1997) 109-119. | MR

[12] D. Ziadi and J.-M. Champarnaud, An optimal parallel algorithm to convert a regular expression into its Glushkov automaton. Theoret. Comput. Sci. 215 (1999) 69-87. | MR | Zbl

[13] D. Ziaidi, J.-L. Ponty and J.-M. Champarnaud, Passage d'une expression rationnelle à un automate fini non-déterministe. Bull. Belg. Math. Soc. 4 (1997) 177-203. | MR | Zbl