Document Open Access Logo

Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Authors Andrew Elvey Price , Wenjie Fang , Michael Wallner

PDF
Thumbnail PDF

File

LIPIcs.AofA.2020.11.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Author Details

Andrew Elvey Price
  • Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique, UMR 5800, 351 Cours de la Libération, 33405 Talence Cedex, France
  • Université de Tours, Institut Denis Poisson, UMR 7013, Parc de Grandmont, 37200 Tours, France
Wenjie Fang
  • Laboratoire d'Informatique Gaspard-Monge, UMR 8049, Université Gustave Eiffel, CNRS, ESIEE Paris, 77454 Marne-la-Vallée, France
Michael Wallner
  • Université de Bordeaux, Laboratoire Bordelais de Recherche en Informatique, UMR 5800, 351 Cours de la Libération, 33405 Talence Cedex, France
  • TU Wien, Institute for Discrete Mathematics and Geometry, Wiedner Hauptstrasse 8 - 10, 1040 Wien, Austria

Funding

  • Elvey Price, Andrew: European Research Council (ERC) in the European Union’s Horizon 2020 research and innovation programme, under the Grant Agreement No. 759702.
  • Fang, Wenjie: Recherche en esprit libre, i.e., not supported by fundings with precise predefined goals.
  • Wallner, Michael: Erwin Schrödinger Fellowship of the Austrian Science Fund (FWF): J 4162-N35.

Acknowledgements

We would like to thank Cyril Banderier, Tony Guttmann, and Andrea Sportiello for interesting discussions on the presence of a stretched exponential. We also thank our referees for their careful reading and helpful comments.

Cite As Get BibTex

Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.AofA.2020.11

Abstract

We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Mathematics of computing → Enumeration
  • Mathematics of computing → Generating functions
Keywords
  • Airy function
  • asymptotics
  • directed acyclic graphs
  • Dyck paths
  • bijection
  • stretched exponential
  • compacted trees
  • minimal automata
  • finite languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Frédérique Bassino, Julien David, and Andrea Sportiello. Asymptotic enumeration of minimal automata. In 29th International Symposium on Theoretical Aspects of Computer Science, volume 14 of LIPIcs. Leibniz Int. Proc. Inform., pages 88-99. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.88.
  2. Frédérique Bassino and Cyril Nicaud. Enumeration and random generation of accessible automata. Theoret. Comput. Sci., 381(1-3):86-104, 2007. URL: https://doi.org/10.1016/j.tcs.2007.04.001.
  3. Mireille Bousquet-Mélou, Markus Lohrey, Sebastian Maneth, and Eric Noeth. XML compression via directed acyclic graphs. Theory Comput. Syst., 57(4):1322-1371, 2015. URL: https://doi.org/10.1007/s00224-014-9544-x.
  4. Michael Domaratzki. Enumeration of formal languages. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 89:117-133, 2006. URL: http://eatcs.org/images/bulletin/beatcs89.pdf.
  5. Michael Domaratzki, Derek Kisman, and Jeffrey Shallit. On the number of distinct languages accepted by finite automata with n states. J. Autom. Lang. Comb., 7(4):469-486, 2002. URL: https://cs.uwaterloo.ca/~shallit/Papers/enum.ps.
  6. Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Compacted binary trees admit a stretched exponential, 2019. URL: http://arxiv.org/abs/1908.11181.
  7. Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner. Asymptotic enumeration of compacted binary trees of bounded right height. J. Combin. Theory Ser. A, 172:105177, 2020. URL: https://doi.org/10.1016/j.jcta.2019.105177.
  8. John E. Hopcroft and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass., 1979. Addison-Wesley Series in Computer Science. Google Scholar
  9. Aleksej D. Korshunov. Enumeration of finite automata. Problemy Kibernet., 34:5-82, 1978. (In Russian). Google Scholar
  10. Aleksej D. Korshunov. On the number of nonisomorphic strongly connected finite automata. Elektron. Informationsverarb. Kybernet., 22(9):459-462, 1986. Google Scholar
  11. Valery A Liskovets. Exact enumeration of acyclic deterministic automata. Discrete Appl. Math., 154(3):537-551, 2006. URL: https://doi.org/10.1016/j.dam.2005.06.009.
  12. Michael Wallner. Personal website, 2020. URL: http://dmg.tuwien.ac.at/mwallner.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact