Computing ε-free NFA from regular expressions in O(nlog 2 (n)) time
Hagenah, Christian ; Muscholl, Anca
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 257-277 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {34},
     year = {2000},
     pages = {257-277},
     mrnumber = {1809860},
     zbl = {0971.68091},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 257-277. http://gdmltest.u-ga.fr/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 889664 | Zbl 0626.68043

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

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

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

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

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

[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 1684071 | Zbl 0912.68113

[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 1473763

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

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

[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 1611986

[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 1678785 | Zbl 0915.68086

[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 1440674 | Zbl 0915.68123