Document Open Access Logo

Improving the Upper Bound on the Length of the Shortest Reset Word

Author Marek Szykula

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.56.pdf
  • Filesize: 441 kB
  • 13 pages

Document Identifiers

Author Details

Marek Szykula

Cite As Get BibTex

Marek Szykula. Improving the Upper Bound on the Length of the Shortest Reset Word. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.56

Abstract

We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than 114 n^3 / 685 + O(n^2). The Cerny conjecture states that (n-1)^2 is an upper bound. So far, the best general upper bound was (n^3-n)/6-1 obtained by J.-E. Pin and P. Frankl in 1982. Despite a number of efforts, it remained unchanged for about 35 years.

To obtain the new upper bound we utilize avoiding words.
A word is avoiding for a state q if after reading the word the automaton cannot be in q. We obtain upper bounds on the length of the shortest avoiding words, and using the approach of Trahtman from 2011 combined with the well-known Frankl theorem from 1982, we improve the general upper bound on the length of the shortest reset words.
For all the bounds, there exist polynomial algorithms finding a word of length not exceeding the bound.

Subject Classification

Keywords
  • avoiding word
  • Cerny conjecture
  • reset length
  • reset threshold
  • reset word
  • synchronizing automaton
  • synchronizing word

Metrics

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

References

  1. D. S. Ananichev and V. V. Gusev. Approximation of Reset Thresholds with Greedy Algorithms. Fundamenta Informaticae, 145(3):221-227, 2016. Google Scholar
  2. D. S. Ananichev and M. V. Volkov. Synchronizing generalized monotonic automata. Theoretical Computer Science, 330(1):3-13, 2005. Google Scholar
  3. M.-P. Béal, M. V. Berlinkov, and D. Perrin. A quadratic upper bound on the size of a synchronizing word in one-cluster automata. International Journal of Foundations of Computer Science, 22(2):277-288, 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. Synchronizing Quasi-Eulerian and Quasi-one-cluster Automata. International Journal of Foundations of Computer Science, 24(6):729-745, 2013. Google Scholar
  6. M. T. Biskup and W. Plandowski. Shortest synchronizing strings for Huffman codes. Theoretical Computer Science, 410(38-40):3925-3941, 2009. Google Scholar
  7. 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
  8. J. Černý, A. Pirická, and B. Rosenauerová. On directable automata. Kybernetica, 7:289-298, 1971. Google Scholar
  9. H. Don. The Černý Conjecture and 1-Contracting Automata. Electronic Journal of Combinatorics, 23(3):P3.12, 2016. Google Scholar
  10. L. Dubuc. Sur les automates circulaires et la conjecture de C̆erný. Informatique théorique et applications, 32:21-34, 1998. In French. Google Scholar
  11. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19:500-510, 1990. Google Scholar
  12. P. Frankl. An extremal problem for two families of sets. European Journal of Combinatorics, 3:125-127, 1982. Google Scholar
  13. F. Gonze, R. M Jungers, and A. N. Trahtman. A Note on a Recent Attempt to Improve the Pin-Frankl Bound. Discrete Mathematics and Theoretical Computer Science, 17(1):307-308, 2015. Google Scholar
  14. M. Grech and A. Kisielewicz. The Černý conjecture for automata respecting intervals of a directed graph. Discrete Mathematics and Theoretical Computer Science, 15(3):61-72, 2013. Google Scholar
  15. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295(1-3):223-232, 2003. Google Scholar
  16. 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
  17. A. A. Klyachko, I. K. Rystsov, and M. A. Spivak. An extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton. Cybernetics, 23(2):165-171, 1987. Google Scholar
  18. P. V. Martugin. A series of slowly synchronizing automata with a zero state over a small alphabet. Information and Computation, 206(9-10):1197-1203, 2008. Google Scholar
  19. J.-E. Pin. Sur les mots synchronisants dans un automate fini. Elektron. Informationsverarb. Kybernet., 14:293-303, 1978. Google Scholar
  20. J.-E. Pin. Utilisation de l'algèbre linéaire en théorie des automates. In Actes du 1er Colloque AFCET-SMF de Mathématiques Appliquées II, AFCET, pages 85-92, 1978. In French. Google Scholar
  21. 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
  22. I. K. Rystsov. Reset words for commutative and solvable automata. Theoretical Computer Science, 172(1-2):273-279, 1997. Google Scholar
  23. P. H. Starke. Eine Bemerkung über homogene Experimente. Elektronishe Informationverarbeitung und Kybernetic, 2:257-259, 1966. In German. Google Scholar
  24. B. Steinberg. The averaging trick and the Černý conjecture. International Journal of Foundations of Computer Science, 22(7):1697-1706, 2011. Google Scholar
  25. B. Steinberg. The Černý conjecture for one-cluster automata with prime length cycle. Theoretical Computer Science, 412(39):5487-5491, 2011. Google Scholar
  26. A. N. Trahtman. The C̆erný conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science, 9(2):3-10, 2007. Google Scholar
  27. A. N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word. In Fundamentals of Computation Theory, volume 6914 of LNCS, pages 173-180. Springer, 2011. Google Scholar
  28. M. V. Volkov. Synchronizing automata and the C̆erný conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
  29. M. V. Volkov. Synchronizing automata preserving a chain of partial orders. Theoretical Computer Science, 410(37):3513-3519, 2009. 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