From regular expressions to finite automataFootnote^∗

^∗This work is a contribution to the Automate software development project carried on by A.I.A. Working Group (Algorithmics and Implementation of Automata) of LIFAR. Contacts:{jmc, ziadi) @dir.univ-rouen.fr

References

• Aho , A. V. , Sethi , R. and Ullman , J. D. 1986 . Compilers , 113 – 158 . Addison-Wesley .
   Google Scholar
• Antimirov , V. 1996 . Partial Derivatives of Regular Expressions and Finite Automaton construction . Theoret, Comput. Sci. , 155 : 291 – 319 .
   Google Scholar
• Autebert , J.-M. 1987 . “ Langages algébriques ” . In Collection Etudes et Recherches en Informatique , Paris : Masson .
   Google Scholar
• Berry , G. and Sethi , R. 1986 . From Regular Expressions to Deterministic Automata . Theoret. Comput. Sci. , 48 : 117 – 126 .
   Web of Science ®Google Scholar
• Berstel , J. 1987 . “ Finite Automata and Rational Languages, an introduction ” . In Formal Properties of Finite Automata and Applications Edited by: Pin , J.-E. Vol. 386 , 2 – 14 . Lecture Notes in Computer Science
   Google Scholar
• Berstel , J. and Pin , J.-E. 1996 . Local Languages and the Berry-Sethi Algorithm . Theoret, Comput, Sci. , 155 : 439 – 446 .
   Google Scholar
• Book , R. , Even , S. , Greibach , S. and Ott , G. 1971 . Ambiguity in Graphs and Expressions . IEEE Trans, on Computers , C-20 ( 2 ) : 149 – 153 .
   Google Scholar
• Brüggemann-Klein , A. 1993 . Regular Expressions into Finite Automata . Theoret. Comput. Sci. , 120 ( 2 ) : 197 – 213 .
   Google Scholar
• Brüggemann-Klein , A. and Wood , D. 1992 . “ Deterministic Regular Languages ” . In Proc. STAGS′92 Edited by: Finkel , A. and Jantzen , M. Vol. 577 , 173 – 184 . Lecture Notes in Computer Science
   Google Scholar
• Brzozowski , J. A. and Mc Cluskey , E. J. Jr. 1963 . Signal Flow Graph Techniques for Sequential Circuit State Diagrams . IEEE Trans, on Electronic Computers , EC 12 ( 2 )
   Google Scholar
• Brzozowski , J. A. 1964 . Derivatives of Regular Expressions . J. ACM , 11 ( 4 ) : 481 – 494 .
   Google Scholar
• Caron , P. 1997 . AG: A Set of Maple Packages of manipulating Automata and Semigroups . Software-Practice and Experience , 27 ( 8 ) : 863 – 884 .
   Web of Science ®Google Scholar
• Caron , P. and Ziadi , D. Characterization of Glushkov Automata . Theoret. Comput. Sci. , to appear in
   Google Scholar
• Champamaud J.-M Automate: Un Système de manipulation des Automates Finis Research report LITP 85-48 1985
   Google Scholar
• Champamaud , J.-M. and Hansel , G. 1991 . Automate: a Computing Package for Automata and Finite Semigroups . J. of Symb. Comp. , 12 ( 8 ) : 197 – 220 .
   Google Scholar
• Champamaud J.-M. Ziadi D. Ponty J.-L Determinization of Glushkov automata Workshop on Implementing Automata, WIA'98, Rouen to appear in Lecture Notes in Computer Science 1988
   Google Scholar
• Chang , C.-H. and Paige , R. 1992 . “ From Regular Expressions to DFAs using NFAs ” . In Proc. CPM′91 Edited by: Apostolica , A. , Crochemore , M. , Galil , Z. and Manber , U. Vol. 664 , 90 – 110 . Lecture Notes in Computer Science
   Google Scholar
• Eilenberg , S. 1974 . “ Automata, Languages, and machines ” . Vol. A , New York : Academic Press .
   Google Scholar
• Glushkov , V. M. 1960 . On a Synthesis Algorithm for Abstract Automata . Ukr, Matem. Zurnal , 12 ( 2 ) : 147 – 156 . in Russian
   Google Scholar
• Glushkov , V M. 1961 . The Abstract Theory of Automata . Russian Mathematical Surveys , 16 ( 2 ) : 1 – 53 .
   Google Scholar
• Hopcroft , J. E. and Ullman , J. D. 1979 . Introduction to Automata Theory, Languages and Computation , Addison-Wesley .
   Google Scholar
• Leiss , E. 1981 . The Complexity of Restricted Regular Expressions and the Synthesis Problem of Finite Automata . J Computer and System Sciences , 23 ( 3 ) : 348 – 354 .
   Web of Science ®Google Scholar
• Matz O. Miller A. Patthoff A Thomas W. Valkena E. Report on the Program AMoRE, Research report Institut für informauk und praktische matheraatik, Christian-Albrechts Universität Kiel 1995
   Google Scholar
• Mc Naughton , R. and Yamada , H. 1960 . Regular Expressions and State Graphs for Automata . IRE Trans. on Electronic Computers , EC-9 ( 3 ) : 39 – 47 .
   Google Scholar
• Mirkin B. G. An Algorithm for constructing a Base in a Language of Regular Expressions, (in Russian) Izv. Akak. Nauk SSSR, Techn. Kibernet 5 1966 113 119 English translation in Engineering Cybernetics, 5, 110-116
   Google Scholar
• Ponty , J.-L. , Ziadi , D. and Champamaud , J.-M. 1997 . “ A new Quadratic Algorithm to convert a Regular Expression into an Automaton ” . In Proc. WIA′96 Edited by: Raymond , D. and Wood , D. Vol. 1260 , 109 – 119 . Lecture Notes in Computer Science
   Google Scholar
• Ponty J.-L. Algorithmique et Implémentation des Automates Contribution au Développement du Logiciel AUTOMATE. Ph.D. Thesis,LIR Université de Rouen France 1997 Rapport LIR TH97.03
   Google Scholar
• Ponty , J.-L. 1988 . “ An Efficient ε-free Procedure for Deciding Regular Language Membership ” . In Proc. WJA′97 Edited by: Wood , D. and Yu , S. Vol. 1436 , 159 – 170 . Lecture Notes in Computer Science
   Google Scholar
• Spivak , M. A. 1963 . A new Algorithm for the Abstract Synthesis of Automata . Materiali Nauchnich Seminarov po Teoreticheskim I Prikladnim Voprosam Kiberneteki, eoria Automatov, Kiev 3. , in Russian
   Google Scholar
• Spivak , M. A. 1965 . An Algorithm for the Abstract Synthesis of Automata for an Extended Language of Regular Expressions . Izv. Akad. Nauk SSSR, Techn. Kibernet , 1 : 51 – 57 . English translation in Engineering Cybernetics.in Russian
   Google Scholar
• Thompson , K. 1968 . Regular Expression Search Algorithm . Comm. Assoc. Comput. Mach. , 11 : 419 – 422 .
   Web of Science ®Google Scholar
• Watson B. Taxonomies and Toolkits of Regular Languages Algorithms, Ph.D. Thesis Eindhoven University of Technology The Nederlands 1995
   Google Scholar
• Wood , D. 1987 . Theory of computation , New York : Wiley .
   Google Scholar
• Ziadi , D. , Ponty , J.-L. and Champamaud , J.-M. 1997 . Passage d′une expression rationnelle à un automate fini non-déterministe . Bull. Belg. Math. Soc. , 4 : 177 – 203 .
   Google Scholar
• Ziadi D. Algorithmique parallèle et séquentielle des automates. Ph.D. Thesis, LIR Université de Rouen France 1996 Rapport LIR TH96.01
   Google Scholar
• Ziadi , D. and Champamaud , J.-M. May 1998 . From Regular Expressions to Small NFAs May , Unpublished manuscript
   Google Scholar