Document Open Access Logo

An Improved Algorithm for Finding the Shortest Synchronizing Words

Authors Marek Szykuła , Adam Zyzik

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.85.pdf
  • Filesize: 0.81 MB
  • 15 pages

Document Identifiers

Author Details

Marek Szykuła
  • Faculty of Mathematics and Computer Science, University of Wrocław, Poland
Adam Zyzik
  • Faculty of Mathematics and Computer Science, University of Wrocław, Poland

Funding

This work was supported in part by the National Science Centre, Poland under project number 2021/41/B/ST6/03691. The experiments were run on a computational grid of the Institute of Computer Science, University of Wrocław, funded by National Science Centre, Poland, under project number 2019/35/B/ST6/04379.

Cite AsGet BibTex

Marek Szykuła and Adam Zyzik. An Improved Algorithm for Finding the Shortest Synchronizing Words. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.85

Abstract

A synchronizing word of a deterministic finite complete automaton is a word whose action maps every state to a single one. Finding a shortest or a short synchronizing word is a central computational problem in the theory of synchronizing automata and is applied in other areas such as model-based testing and the theory of codes. Because the problem of finding a shortest synchronizing word is computationally hard, among exact algorithms only exponential ones are known. We redesign the previously fastest known exact algorithm based on the bidirectional breadth-first search and improve it with respect to time and space in a practical sense. We develop new algorithmic enhancements and adapt the algorithm to multithreaded and GPU computing. Our experiments show that the new algorithm is multiple times faster than the previously fastest one and its advantage quickly grows with the hardness of the problem instance. Given a modest time limit, we compute the lengths of the shortest synchronizing words for random binary automata up to 570 states, significantly beating the previous record. We refine the experimental estimation of the average reset threshold of these automata. Finally, we develop a general computational package devoted to the problem, where an efficient and practical implementation of our algorithm is included, together with several well-known heuristics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Formal languages and automata theory
Keywords
  • Čern{ý} conjecture
  • reset threshold
  • reset word
  • subset checking
  • synchronizing automaton
  • synchronizing word

Metrics

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

Related Versions

Supplementary Materials

References

  1. D. S. Ananichev and M. V. Volkov. Synchronizing monotonic automata. In Developments in Language Theory, volume 2710 of LNCS, pages 111-121. Springer, 2003. Google Scholar
  2. 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
  3. R. J. Bayardo and B. Panda. Fast Algorithms for Finding Extremal Sets, pages 25-34. SIAM, 2011. Google Scholar
  4. M. Berlinkov and M. Szykuła. Algebraic synchronization criterion and computing reset words. Information Sciences, 369:718-730, 2016. Google Scholar
  5. M. V. Berlinkov. On the Probability of Being Synchronizable. In Proceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 9602, volume 9602 of CALDAM, pages 73-84. Springer, 2016. Google Scholar
  6. 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
  7. J. Berstel, D. Perrin, and C. Reutenauer. Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009. Google Scholar
  8. J. Černý. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208-216, 1964. In Slovak. Google Scholar
  9. M. de Bondt, H Don, and H. Zantema. Lower Bounds for Synchronizing Word Lengths in Partial Automata. Int. J. Found. Comput. Sci., 30(1):29-60, 2019. Google Scholar
  10. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19:500-510, 1990. Google Scholar
  11. H. Fernau, P. Heggernes, and Y. Villanger. A multi-parameter analysis of hard problems on deterministic finite automata. Journal of Computer and System Sciences, 81(4):747-765, 2015. Google Scholar
  12. P. Gawrychowski and D. Straszak. Strong inapproximability of the shortest reset word. In Mathematical Foundations of Computer Science, volume 9234 of LNCS, pages 243-255. Springer, 2015. Google Scholar
  13. M. Gerbush and B. Heeringa. Approximating minimum reset sequences. In Implementation and Application of Automata, volume 6482 of LNCS, pages 154-162. Springer, 2011. Google Scholar
  14. B. Gerencsér, V. V. Gusev, and R. M. Jungers. Primitive Sets of Nonnegative Matrices and Synchronizing Automata. SIAM J. Matrix Anal. Appl., 39(1):83-98, 2018. Google Scholar
  15. H. Jürgensen. Synchronization. Information and Computation, 206(9-10):1033-1044, 2008. Google Scholar
  16. D. M Kane and R. R. Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  17. J. Kari. Synchronization and stability of finite automata. Journal of Universal Computer Science, 8(2):270-277, 2002. Google Scholar
  18. 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
  19. A. Kisielewicz, J. Kowalski, and M. Szykuła. A Fast Algorithm Finding the Shortest Reset Words. In COCOON, volume 7936 of LNCS, pages 182-196, 2013. Google Scholar
  20. A. Kisielewicz, J. Kowalski, and M. Szykuła. Computing the shortest reset words of synchronizing automata. Journal of Combinatorial Optimization, 29(1):88-124, 2015. Google Scholar
  21. A. Kisielewicz, J. Kowalski, and M. Szykuła. Experiments with Synchronizing Automata. In Implementation and Application of Automata, volume 9705 of LNCS, pages 176-188. Springer, 2016. Google Scholar
  22. J. Kowalski and A. Roman. A new evolutionary algorithm for synchronization. In Giovanni Squillero and Kevin Sim, editors, Applications of Evolutionary Computation, pages 620-635. Springer, 2017. Google Scholar
  23. R. Kudłacik, A. Roman, and H. Wagner. Effective synchronizing algorithms. Expert Systems with Applications, 39(14):11746-11757, 2012. Google Scholar
  24. C. Nicaud. Fast Synchronization of Random Automata. In Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans, editors, APPROX/RANDOM 2016, volume 60 of LIPIcs, pages 43:1-43:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  25. J. Olschewski and M. Ummels. The complexity of finding reset words in finite automata. In Mathematical Foundations of Computer Science 2010, volume 6281 of LNCS, pages 568-579. Springer, 2010. Google Scholar
  26. 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
  27. I. Podolak, A. Roman, M. Szykuła, and B. Zieliński. A machine learning approach to synchronization of automata. Expert Systems with Applications, 97:357-371, 2018. Google Scholar
  28. I. T. Podolak, A. Roman, and D. Jędrzejczyk. Application of hierarchical classifier to minimal synchronizing word problem. In Artificial Intelligence and Soft Computing, volume 7267 of LNCS, pages 421-429. Springer, 2012. Google Scholar
  29. I. Pomeranz and S.M. Reddy. On achieving complete testability of synchronous sequential circuits with synchronizing sequences. IEEE Proc. International Test Conference, pages 1007-1016, 1994. Google Scholar
  30. A. Roman and M. Szykuła. Forward and backward synchronizing algorithms. Expert Systems with Applications, 42(24):9512-9527, 2015. Google Scholar
  31. I. K. Rystsov. Reset words for commutative and solvable automata. Theoretical Computer Science, 172(1-2):273-279, 1997. Google Scholar
  32. A. Ryzhikov. Mortality and Synchronization of Unambiguous Finite Automata. In Robert Mercaş and Daniel Reidenbach, editors, Combinatorics on Words, pages 299-311. Springer International Publishing, 2019. Google Scholar
  33. A. Ryzhikov and M. Szykuła. Finding Short Synchronizing Words for Prefix Codes. In MFCS 2018, volume 117 of LIPIcs, pages 21:1-21:14. Schloss Dagstuhl, 2018. Google Scholar
  34. S. Sandberg. Homing and synchronizing sequences. In Model-Based Testing of Reactive Systems, volume 3472 of LNCS, pages 5-33. Springer, 2005. Google Scholar
  35. N. E. Saraç, O. F. Altun, K. T. Atam, S. Karahoda, K. Kaya, and H. Yenigün. Boosting expensive synchronizing heuristics. Expert Systems with Applications, 167:114203, 2021. Google Scholar
  36. H. Shabana. Exact synchronization in partial deterministic automata. Journal of Physics: Conference Series, 1352:012047, 2019. Google Scholar
  37. 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
  38. E. Skvortsov and E. Tipikin. Experimental study of the shortest reset word of random automata. In Implementation and Application of Automata, volume 6807 of LNCS, pages 290-298. Springer, 2011. Google Scholar
  39. 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 fuer Informatik, 2018. Google Scholar
  40. M. Szykuła and A. Zyzik. Synchrowords. https://github.com/marekesz/synchrowords, 2022.
  41. M. K. Taş, K. Kaya, and H. Yenigün. Synchronizing billion-scale automata. Information Sciences, 574:162-175, 2021. Google Scholar
  42. A. N. Trahtman. An efficient algorithm finds noticeable trends and examples concerning the Cerný conjecture. In Mathematical Foundations of Computer Science, volume 4162 of LNCS, pages 789-800. Springer, 2006. Google Scholar
  43. N. F. Travers and J. P. Crutchfield. Exact Synchronization for Finite-State Sources. Journal of Statistical Physics, 145(5):1181-1201, 2011. Google Scholar
  44. M. 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
  45. M. V. Volkov, editor. Special Issue: Essays on the Černý Conjecture, volume 24 (2-4) of Journal of Automata, Languages and Combinatorics, 2019. Google Scholar
  46. V. Vorel. Subset Synchronization and Careful Synchronization of Binary Finite Automata. International Journal of Foundations of Computer Science, 27(05):557-577, 2016. Google Scholar
  47. V. Vorel. Complexity of a problem concerning reset words for Eulerian binary automata. Information and Computation, 253:497-509, 2017. 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 Imprint Privacy Contact