From Glushkov WFAs to Rational Expressions

  • Pascal Caron
  • Marianne Flouret
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


In this paper, we extend to the multiplicity case a characterization of Glushkov automata, and show the existence of a normal form for rational expressions. These results are used to obtain a rational expression of small size from a Glushkov WFA.


Normal Form Rational Expression Regular Expression Rational Series Weighted Graph 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    J. Berstel and C. Reutenauer. Rational series and their languages. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1988.Google Scholar
  2. 2.
    R. Book, S. Even, S. Greibach, and G. Ott. Ambiguity in graphs and expressions. IEEE Trans. Comput., c-20(2):149–153, 1971.CrossRefMathSciNetGoogle Scholar
  3. 3.
    A. Brüggemann-Klein. Regular expressions into finite automata. Theoret. Comput. Sci., 120(1):197–213, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    A. Buchsbaum, R. Giancarlo, and J. Westbrook. On the determinization of weighted finite automata. SIAM J. Comput., 30(5):1502–1531, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  5. 5.
    P. Caron and M. Flouret. Glushkov construction for series: the non commutative case. Internat. J. Comput. Math. To appear.Google Scholar
  6. 6.
    P. Caron and M. Flouret. Star normal form, rational expressions and glushkov WFAs properties. In Seventh International Conference on Implementation and Application of Automata, CIAA’02.Google Scholar
  7. 7.
    P. Caron and D. Ziadi. Characterization of Glushkov automata. Theoret. Comput. Sci., 233(1–2):75–90, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    S. Eilenberg. Automata, languages and machines, volume A. Academic Press, New York, 1974.zbMATHGoogle Scholar
  9. 9.
    K. Culik II and J. Kari. Digital images and formal languages. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, pages 599–616. svb, 1997.Google Scholar
  10. 10.
    S. Lombardy and J. Sakarovitch. Derivatives of regular expression with multiplicity. Technical Report 2001D001, ENST, Paris, 2001.Google Scholar
  11. 11.
    R.F. McNaughton and H. Yamada. Regular expressions and state graphs for automata. IEEE Transactions on Electronic Computers, 9:39–57, March 1960.CrossRefGoogle Scholar
  12. 12.
    M. Mohri. Finite-state transducers in language and speech processing. Computat. Ling., 23.2:269–311, 1997.MathSciNetGoogle Scholar
  13. 13.
    F. Pereira and M. Riley. Speech recognition by composition of weighted finite automata. In E. Roche and Y. Schabes, editors, Finite state language processing, pages 431–453, Cambridge, Massachusetts, 1997. M.I.T. Press.Google Scholar
  14. 14.
    M.P. Schützenberger. On the definition of a family of automata. Inform. and Control, 4:245–270, 1961.zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Pascal Caron
    • 1
  • Marianne Flouret
    • 2
  1. 1.LIFARUniversité de RouenMont-Saint-Aignan CedexFrance
  2. 2.LIHUniversité du HavreLe Havre CedexFrance

Personalised recommendations