On the Average Size of Glushkov’s Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the Average Size of Glushkov’s Automata

  • Conference paper
Language and Automata Theory and Applications (LATA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5457))

Abstract

Glushkov’s algorithm builds an ε-free nondeterministic automaton from a given regular expression. In the worst case, its number of states is linear and its number of transitions is quadratic in the size of the expression. We show in this paper that in average, the number of transitions is linear.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Sakarovitch, J.: The language, the expression, and the (Small) automaton. In: Farré, J., Litovsky, I., Schmitz, S. (eds.) CIAA 2005. LNCS, vol. 3845, pp. 15–30. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  2. Glushkov, V.M.: The abstract theory of automata. Russian Math. Surveys 16, 1–53 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  3. Hromkovic, J., Seibert, S., Wilke, T.: Translating regular expressions into small epsilon-free nondeterministic finite automata. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 55–66. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  4. Hagenah, C., Muscholl, A.: Computing epsilon-free NFA from regular expressions in O(n log2(n)) time. ITA 34(4), 257–278 (2000)

    MATH  Google Scholar 

  5. Ilie, L., Yu, S.: Constructing NFAs by optimal use of positions in regular expressions. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 279–288. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  6. Champarnaud, J.M., Nicart, F., Ziadi, D.: Computing the follow automaton of an expression. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 90–101. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2008)

    MATH  Google Scholar 

  8. Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)

    MATH  Google Scholar 

  9. Flajolet, P., Odlyzko, A.M.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25(2), 171–213 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  10. Lee, J., Shallit, J.: Enumerating regular expressions and their languages. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 2–22. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. Fernández-Camacho, M.I., Steyaert, J.M.: Algebraic simplification in computer algebra: An analysis of bottom-up algorithms. TCS 74(3), 273–298 (1990)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIGM, UMR CNRS 8049, Université Paris Est, 77454, Marne-la-Vallée, France

    Cyril Nicaud

Authors
  1. Cyril Nicaud
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain

    Adrian Horia Dediu

  2. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain

    Armand Mihai Ionescu

  3. European Research Council Executive Agency, 16 Place Rogier, 1210, Brussels, Belgium

    Carlos Martín-Vide

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nicaud, C. (2009). On the Average Size of Glushkov’s Automata. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_53

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-00982-2_53

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00981-5

  • Online ISBN: 978-3-642-00982-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics