Computing ε -free NFA from regular expressions in O ( n log 2 ( n ) ) time

Christian Hagenah; Anca Muscholl

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

  • Volume: 34, Issue: 4, page 257-277
  • ISSN: 0988-3754

How to cite

top

Hagenah, Christian, and 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 34.4 (2000): 257-277. <http://eudml.org/doc/92634>.

@article{Hagenah2000,
author = {Hagenah, Christian, Muscholl, Anca},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {nondeterministic finite automaton},
language = {eng},
number = {4},
pages = {257-277},
publisher = {EDP-Sciences},
title = {Computing $\varepsilon $-free NFA from regular expressions in $O(n \log ^2 (n))$ time},
url = {http://eudml.org/doc/92634},
volume = {34},
year = {2000},
}

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
PB - EDP-Sciences
VL - 34
IS - 4
SP - 257
EP - 277
LA - eng
KW - nondeterministic finite automaton
UR - http://eudml.org/doc/92634
ER -

References

top
  1. [1] G. Berry and R. Sethi, From regular expressions to deterministic automata. Theoret. Comput. Sci. 48 (1986) 117-126. Zbl0626.68043MR889664
  2. [2] J. Berstel and J.-É. Pin, Local languages and the Berry-Sethi algorithm. Theoret. Comput. Sci. 155 (1996) 439-446. Zbl0872.68116MR1379585
  3. [3] A. Brüggemann-Klein, Regular expressions into finite automata. Theoret. Comput. Sci. 120 (1993) 197-213. Zbl0811.68096MR1247207
  4. [4] A. Ehrenfeucht and P. Zeiger, Complexity measures for regular expressions. J. Comput. System Sci. 12 (1976) 134-146. Zbl0329.94024MR418509
  5. [5] A. Gibbons and W. Rytter, Efficient parallel algorithms. Cambridge University Press (1989). Zbl0771.68015MR1110582
  6. [6] V. M. Glushkov, The abstract theory of automata. Russian Math. Surveys 16 (1961) 1-53. Zbl0104.35404MR138529
  7. [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. Zbl0912.68113MR1684071
  8. [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. MR1473763
  9. [9] J. JáJá, An introduction to parallel algorithms. Addison-Wesley, Reading, MA (1992). Zbl0781.68009
  10. [10] R. McNaughton and H. Yamada, Regular expressions and state graphs for automata. IRE Trans. Electron. Comput. EC-9 (1960) 39-47. Zbl0156.25501
  11. [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. MR1611986
  12. [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. Zbl0915.68086MR1678785
  13. [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. Zbl0915.68123MR1440674

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.