The Černý (1969) conjecture holds for quasi-Eulerian automata of degree one

A mix of human-written and AI-generated textHuman understanding: some partscs.FL — Formal Languages and Automata Theorymath.CO — Combinatorics

Contributed by Dave Goel ↗

Version 1 / Nov 19, 2026 / CC BY-SA 4.0

Abstract

An automaton with nn states is quasi-Eulerian of degree dd if there are positive letter weights summing to one, a set XX of dd exceptional states and a further state ss such that every state outside X∪{s}X\cup\{s\} receives total weight one and every edge that starts in XX ends in X∪{s}X\cup\{s\}. Berlinkov bounded the reset threshold of strongly connected synchronizing ones by 2d(n−d+1)(n−1)2^d(n-d+1)(n-1). We prove that every synchronizing quasi-Eulerian automaton of degree one has a reset word of length at most (n−1)2(n-1)^2, 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 2n(n−1)2n(n-1). 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 4646 of the 4949 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 KK of states that contains it has length at most ∣K∣|K|, and one that takes it into a set KK that does not contain it has length at most n−∣K∣n-|K|.

Author comments: First version: October 24, 2026.

Provenance statement

This work was done overwhelmingly by AI models, steered by the author in a continuous critical dialogue, alternating between Anthropic's Claude and OpenAI's ChatGPT. The author takes full responsibility for the paper.

References

  1. 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
  2. M. V. Berlinkov, Synchronizing quasi-Eulerian and quasi-one-cluster automata , Internat. J. Found. Comput. Sci. 24(6) (2013), 729--745.
  3. 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.
  4. J. Černý, A. Pirická and B. Rosenauerová, On directable automata , Kybernetika 7(4) (1971), 289--298.
  5. P. Frankl, An extremal problem for two families of sets , European J. Combin. 3(2) (1982), 125--127.
  6. 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.
  7. J. Kari, Synchronizing finite automata on Eulerian digraphs , Theoret. Comput. Sci. 295(1--3) (2003), 223--232.
  8. 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
  9. J.-E. Pin, On two combinatorial problems arising from automata theory , Ann. Discrete Math. 17 (1983), 535--548.
  10. 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
  1. B. Steinberg, The averaging trick and the Černý conjecture , Internat. J. Found. Comput. Sci. 22(7) (2011), 1697--1706.
  2. 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.
  3. 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
  4. 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.
  5. M. V. Volkov, Synchronization of finite automata , Russian Math. Surveys 77(5) (2022), 819--891.
  6. M. V. Volkov, List of results on the Černý conjecture and reset thresholds for synchronizing automata , arXiv:2508.15655v4 (2026).arXiv
  7. Y. Zhu, The Černý conjecture for one-cluster automata via annular spectral descent , arXiv:2607.19675 (2026).arXiv

Version history

  1. v1 · 20 pagesSubmitted by Dave GoelFirst version: October 24, 2026.CurrentNov 19, 2026