The Černý (1969) conjecture holds for quasi-Eulerian automata of degree one
Version 1 / Nov 19, 2026 / CC BY-SA 4.0
Abstract
An automaton with states is quasi-Eulerian of degree if there are positive letter weights summing to one, a set of exceptional states and a further state such that every state outside receives total weight one and every edge that starts in ends in . Berlinkov bounded the reset threshold of strongly connected synchronizing ones by . We prove that every synchronizing quasi-Eulerian automaton of degree one has a reset word of length at most , so the Černý (1969) conjecture holds for this family; the Černý automata belong to it and attain the bound. The same bound holds for every synchronizing automaton whose transition matrix, weighted by some positive, possibly irrational, letter weights, has a positive stationary vector that is constant on all states but one; for this family Berlinkov's bound was . For synchronizing quasi-Eulerian automata of degree two, the bound holds whenever the automaton is not strongly connected, whenever its two exceptional states form a block of a congruence, and, for binary strongly connected automata, in of the configurations (up to renaming) of the edges at the two exceptional states. The key step in degree one is elementary: a shortest word that takes the exceptional state out of a set of states that contains it has length at most , and one that takes it into a set that does not contain it has length at most .
Provenance statement
References
- M. V. Berlinkov, Synchronizing automata on quasi Eulerian digraph , arXiv:1203.3402v1 (2012; statement numbers as in this version); conference version in: Implementation and Application of Automata (CIAA 2012), Lecture Notes in Comput. Sci. 7381, Springer (2012), 90--100.arXiv
- M. V. Berlinkov, Synchronizing quasi-Eulerian and quasi-one-cluster automata , Internat. J. Found. Comput. Sci. 24(6) (2013), 729--745.
- J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi , Mat.-Fyz. Časopis Sloven. Akad. Vied 14(3) (1964), 208--216; English translation: A note on homogeneous experiments with finite automata , J. Autom. Lang. Comb. 24(2--4) (2019), 123--132.
- J. Černý, A. Pirická and B. Rosenauerová, On directable automata , Kybernetika 7(4) (1971), 289--298.
- P. Frankl, An extremal problem for two families of sets , European J. Combin. 3(2) (1982), 125--127.
- V. V. Gusev and E. V. Pribavkina, On synchronizing colorings and the eigenvectors of digraphs , in: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs 58 (2016), 48:1--48:14.
- J. Kari, Synchronizing finite automata on Eulerian digraphs , Theoret. Comput. Sci. 295(1--3) (2003), 223--232.
- A. Kisielewicz, J. Kowalski and M. Szykuła, Experiments with synchronizing automata , in: Implementation and Application of Automata (CIAA 2016), Lecture Notes in Comput. Sci. 9705, Springer (2016), 176--188; arXiv:1607.04025.arXiv
- J.-E. Pin, On two combinatorial problems arising from automata theory , Ann. Discrete Math. 17 (1983), 535--548.
- Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata , J. Autom. Lang. Comb. 24(2--4) (2019), 367--373.
Show all 17 referencesShow fewer references
- B. Steinberg, The averaging trick and the Černý conjecture , Internat. J. Found. Comput. Sci. 22(7) (2011), 1697--1706.
- M. Szykuła, Improving the upper bound on the length of the shortest reset word , in: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), LIPIcs 96 (2018), 56:1--56:13.
- M. Szykuła, Synchronizing automata: open problems , in: 17th International Conference on Automata and Formal Languages (AFL 2026), EPTCS 451 (2026), 33--47; arXiv:2608.24245.arXiv
- M. V. Volkov, Synchronizing automata and the Černý conjecture , in: Language and Automata Theory and Applications (LATA 2008), Lecture Notes in Comput. Sci. 5196, Springer (2008), 11--27.
- M. V. Volkov, Synchronization of finite automata , Russian Math. Surveys 77(5) (2022), 819--891.
- M. V. Volkov, List of results on the Černý conjecture and reset thresholds for synchronizing automata , arXiv:2508.15655v4 (2026).arXiv
- Y. Zhu, The Černý conjecture for one-cluster automata via annular spectral descent , arXiv:2607.19675 (2026).arXiv