Document Open Access Logo

One Drop of Non-Determinism in a Random Deterministic Automaton

Authors Arnaud Carayol, Philippe Duchon, Florent Koechlin, Cyril Nicaud

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.19.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Arnaud Carayol
  • Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France
Philippe Duchon
  • Univ. Bordeaux, CNRS UMR 5800, LaBRI, F-33400 Talence, France
Florent Koechlin
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Cyril Nicaud
  • Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

Acknowledgements

The authors would like to thank the reviewers for their helpful comments.

Cite As Get BibTex

Arnaud Carayol, Philippe Duchon, Florent Koechlin, and Cyril Nicaud. One Drop of Non-Determinism in a Random Deterministic Automaton. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.STACS.2023.19

Abstract

Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this article, we investigate this classical result in a probabilistic setting where we take a deterministic automaton with n states uniformly at random and add just one random transition. These automata are almost deterministic in the sense that only one state has a non-deterministic choice when reading an input letter. In our model each state has a fixed probability to be final. We prove that for any d ≥ 1, with non-negligible probability the minimal (deterministic) automaton of the language recognized by such an automaton has more than n^d states; as a byproduct, the expected size of its minimal automaton grows faster than any polynomial. Our result also holds when each state is final with some probability that depends on n, as long as it is not too close to 0 and 1, at distance at least Ω(1/√n) to be precise, therefore allowing models with a sublinear number of final states in expectation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Probability and statistics
Keywords
  • non-deterministic automaton
  • powerset construction
  • probabilistic analysis

Metrics

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

References

  1. Louigi Addario-Berry, Borja Balle, and Guillem Perarnau Llobet. Diameter and stationary distribution of random r-out digraphs. Electronic journal of combinatorics, 27(P3. 28):1-41, 2020. Google Scholar
  2. Frédérique Bassino, Julien David, and Cyril Nicaud. Average case analysis of Moore’s state minimization algorithm. Algorithmica, 63(1-2):509-531, 2012. URL: https://doi.org/10.1007/s00453-011-9557-7.
  3. Frédérique Bassino, Julien David, and Andrea Sportiello. Asymptotic enumeration of minimal automata. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 88-99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.88.
  4. Mikhail V. Berlinkov. On the probability of being synchronizable. In Sathish Govindarajan and Anil Maheshwari, editors, Algorithms and Discrete Applied Mathematics - Second International Conference, CALDAM 2016, Thiruvananthapuram, India, February 18-20, 2016, Proceedings, volume 9602 of Lecture Notes in Computer Science, pages 73-84. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-29221-2_7.
  5. Xing Shi Cai and Luc Devroye. The graph structure of a deterministic automaton chosen at random. Random Structures & Algorithms, 51(3):428-458, 2017. Google Scholar
  6. Arnaud Carayol and Cyril Nicaud. Distribution of the number of accessible states in a random deterministic automaton. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 194-205. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.194.
  7. Guillaume Chapuy and Guillem Perarnau. Short synchronizing words for random automata. CoRR, abs/2207.14108, 2022. URL: https://doi.org/10.48550/arXiv.2207.14108.
  8. Julien David. Average complexity of Moore’s and Hopcroft’s algorithms. Theor. Comput. Sci., 417:50-65, 2012. URL: https://doi.org/10.1016/j.tcs.2011.10.011.
  9. Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960. Google Scholar
  10. Sven De Felice and Cyril Nicaud. Brzozowski algorithm is generically super-polynomial for deterministic automata. In Marie-Pierre Béal and Olivier Carton, editors, Developments in Language Theory - 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings, volume 7907 of Lecture Notes in Computer Science, pages 179-190. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38771-5_17.
  11. Sven De Felice and Cyril Nicaud. Average case analysis of Brzozowski’s algorithm. Int. J. Found. Comput. Sci., 27(2):109-126, 2016. URL: https://doi.org/10.1142/S0129054116400025.
  12. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  13. Aleksandr Aleksandrovich Grusho. Limit distributions of certain characteristics of random automaton graphs. Mathematical Notes of the Academy of Sciences of the USSR, 14(1):633-637, 1973. Google Scholar
  14. J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. Google Scholar
  15. Florent Koechlin, Cyril Nicaud, and Pablo Rotondo. Simplifications of uniform expressions specified by systems. Int. J. Found. Comput. Sci., 32(6):733-760, 2021. Google Scholar
  16. Lothaire. Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, 2 edition, 1997. URL: https://doi.org/10.1017/CBO9780511566097.
  17. Albert R Meyer and Michael J Fischer. Economy of description by automata, grammars, and formal systems. In 12th Annual Symposium on Switching and Automata Theory (SWAT 1971), pages 188-191. IEEE Computer Society, 1971. Google Scholar
  18. Cyril Nicaud. Random deterministic automata. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 5-23. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44522-8_2.
  19. Cyril Nicaud. The Černý conjecture holds with high probability. J. Autom. Lang. Comb., 24(2-4):343-365, 2019. URL: https://doi.org/10.25596/jalc-2019-343.
  20. László Tóth. The probability that k positive integers are pairwise relatively prime. Fibonacci Quart, 40:13-18, 2002. Google Scholar
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