Document Open Access Logo

Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds

Authors Robert Ferens , Marek Szykuła

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.59.pdf
  • Filesize: 0.77 MB
  • 17 pages

Document Identifiers

Author Details

Robert Ferens
  • University of Wrocław, Poland
Marek Szykuła
  • University of Wrocław, Poland

Funding

  • Ferens, Robert: Supported in part by the National Science Centre, Poland under project number 2017/26/E/ST6/00191.
  • Szykuła, Marek: Supported in part by the National Science Centre, Poland under project number 2021/41/B/ST6/03691.

Acknowledgements

We thank the anonymous reviewer for careful proofreading and his suggestions.

Cite As Get BibTex

Robert Ferens and Marek Szykuła. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.59

Abstract

A complete deterministic finite (semi)automaton (DFA) with a set of states Q is completely reachable if every non-empty subset of Q can be obtained as the image of the action of some word applied to Q. The concept of completely reachable automata appeared several times, in particular, in connection with synchronizing automata; the class contains the Černý automata and covers a few separately investigated subclasses. The notion was introduced by Bondar and Volkov (2016), who also raised the question about the complexity of deciding if an automaton is completely reachable. We develop a polynomial-time algorithm for this problem, which is based on a new complement-intersecting technique for finding an extending word for a subset of states. The algorithm works in 𝒪(|Σ|⋅ n³) time, where n = |Q| is the number of states and |Σ| is the size of the input alphabet. Finally, we prove a weak Don’s conjecture for this class of automata: a subset of size k is reachable with a word of length smaller than 2n(n-k). This implies a quadratic upper bound in n on the length of the shortest synchronizing words (reset threshold) for the class of completely reachable automata and generalizes earlier upper bounds derived for its subclasses.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
  • Mathematics of computing → Combinatorics
  • Theory of computation → Formal languages and automata theory
Keywords
  • Černý conjecture
  • complete reachability
  • DFA
  • extending word
  • reachability
  • reset threshold
  • reset word
  • simple idempotent
  • synchronizing automaton
  • synchronizing word

Metrics

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

Related Versions

References

  1. D. S. Ananichev, M. V. Volkov, and V. V. Gusev. Primitive digraphs with large exponents and slowly synchronizing automata. Journal of Mathematical Sciences, 192(3):263-278, 2013. Google Scholar
  2. M. V. Berlinkov, R. Ferens, A. Ryzhikov, and M. Szykuła. Synchronizing Strongly Connected Partial DFAs. In STACS, volume 187 of LIPIcs, pages 12:1-12:16. Schloss Dagstuhl, 2021. Google Scholar
  3. M. V. Berlinkov, R. Ferens, and M. Szykuła. Preimage problems for deterministic finite automata. Journal of Computer and System Sciences, 115:214-234, 2021. Google Scholar
  4. J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  5. E. A. Bondar, D. Casas, and M. V. Volkov. Completely reachable automata: an interplay between automata, graphs, and trees, 2022. URL: https://arxiv.org/abs/2201.05075.
  6. E. A. Bondar and M. V. Volkov. Completely Reachable Automata. In Cezar Câmpeanu, Florin Manea, and Jeffrey Shallit, editors, DCFS, pages 1-17. Springer, 2016. Google Scholar
  7. E. A. Bondar and M. V. Volkov. A Characterization of Completely Reachable Automata. In Mizuho Hoshi and Shinnosuke Seki, editors, DLT, pages 145-155. Springer, 2018. Google Scholar
  8. D. Casas and M. V. Volkov. Binary completely reachable automata. In Armando Castañeda and Francisco Rodríguez-Henríquez, editors, LATIN 2022: Theoretical Informatics, pages 345-358. Springer, 2022. Full version at URL: https://arxiv.org/abs/2205.09404.
  9. J. Černý. Poznámka k homogénnym experimentom s konečnými automatami. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208-216, 1964. In Slovak. Google Scholar
  10. H. Don. The Černý Conjecture and 1-Contracting Automata. Electronic Journal of Combinatorics, 23(3):P3.12, 2016. Google Scholar
  11. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19:500-510, 1990. Google Scholar
  12. R. Ferens, M. Szykuła, and V. Vorel. Lower Bounds on Avoiding Thresholds. In MFCS, volume 202 of LIPIcs, pages 46:1-46:14. Schloss Dagstuhl, 2021. Google Scholar
  13. F. Gonze, V. V. Gusev, B. Gerencser, R. M. Jungers, and M. V. Volkov. On the interplay between Babai and Černý’s conjectures. In DLT, volume 10396 of LNCS, pages 185-197. Springer, 2017. Google Scholar
  14. F. Gonze and R. M. Jungers. Hardly reachable subsets and completely reachable automata with 1-deficient words. Journal of Automata, Languages and Combinatorics, 24(2-4):321-342, 2019. Google Scholar
  15. S. Hoffmann. Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, LATA, LNCS, pages 305-317. Springer, 2021. Google Scholar
  16. J. Kari and M. V. Volkov. Černý conjecture and the road colouring problem. In Handbook of automata, volume 1, pages 525-565. European Mathematical Society Publishing House, 2021. Google Scholar
  17. M. Maslennikova. Reset complexity of ideal languages over a binary alphabet. International Journal of Foundations of Computer Science, 30(06n07):1177-1196, 2019. Google Scholar
  18. J.-E. Pin. On two combinatorial problems arising from automata theory. In Proceedings of the International Colloquium on Graph Theory and Combinatorics, volume 75 of North-Holland Mathematics Studies, pages 535-548, 1983. Google Scholar
  19. I.K. Rystsov. Estimation of the length of reset words for automata with simple idempotents. Cybern. Syst. Anal. 36, pages 339-344, 2000. Google Scholar
  20. S. Sandberg. Homing and synchronizing sequences. In Model-Based Testing of Reactive Systems, volume 3472 of LNCS, pages 5-33. Springer, 2005. Google Scholar
  21. Y. Shitov. An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata. Journal of Automata, Languages and Combinatorics, 24(2-4):367-373, 2019. Google Scholar
  22. M. Szykuła. Improving the Upper Bound on the Length of the Shortest Reset Word. In STACS 2018, LIPIcs, pages 56:1-56:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  23. M. Szykuła and A. Zyzik. An Improved Algorithm for Finding the Shortest Synchronizing Words. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 85:1-85:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  24. M. V. Volkov. Synchronizing automata and the Černý conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
  25. M. V. Volkov. Synchronization of finite automata. Uspekhi Matematicheskikh Nauk, 77:53-130, 2022. in Russian. 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