The Černý conjecture on synchronizing automata

A finite automaton is synchronizing if some sequence of inputs drives it into one and the same state wherever it starts, like a reset button for a machine whose state is unknown. Černý conjectured that for an automaton with $n$ states, a reset sequence of length $(n-1)^2$ always suffices, which would be exactly tight. More than sixty years later the best general bound is still cubic in $n$.

Problem

A complete deterministic finite automaton consists of a finite set of states $Q$ with $|Q| = n$, a finite input alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \to Q$, extended to words letter by letter. A word $w$ is synchronizing (or a reset word) if $\delta(q, w)$ is the same state for every $q \in Q$, and the automaton is synchronizing if it has such a word.

Conjecture (Černý). Every synchronizing automaton with $n$ states has a synchronizing word of length at most $(n - 1)^2$.

Background

Ján Černý (1964) described, for each $n$, an automaton whose shortest synchronizing word has length exactly $(n-1)^2$, and the conjecture that no automaton is worse is attributed to him in the 1960s. It is one of the best-known open problems in automata theory: easy to state, testable by computer for small $n$, and resistant to general methods. Volkov's survey describes its history and the special classes of automata for which it is known.

What is known

• Every synchronizing automaton with $n$ states has a reset word of length at most $\alpha n^3 + o(n^3)$ for an absolute constant $\alpha$. Pin and Frankl (1982) gave $\alpha = 1/6$; Szykuła (2017) lowered it to about $0.1664$, and Shitov (2019) to $\alpha \le 0.1654$, the best bound known.
• The Černý automata show that $(n-1)^2$ cannot be lowered.
• The bound $(n-1)^2$ has been verified for small $n$ and proved for special classes, for example Eulerian, aperiodic and cyclic automata, as recorded in the formal-conjectures file. A July 2026 preprint (Zhu, unrefereed, obtained with AI assistance) claims it for one-cluster automata.

What would count as progress

• A counterexample: an automaton with $n$ states whose shortest reset word is longer than $(n-1)^2$. Its reset threshold can be computed exactly by breadth-first search over subsets of states, so any candidate is checkable.
• A better constant in the cubic bound, or a bound of order $n^{3 - \varepsilon}$.
• Proofs of the quadratic bound for further natural classes of automata, or extended exhaustive verification for small $n$ and alphabet sizes, with published code.
• A formal proof of the Lean statement cerny_conjecture, or of Shitov's bound stated in the same file, Wikipedia/CernyConjecture.lean.

References

1. J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi, Mat.-fyz. časopis 14 (1964), 208–216.
2. M. V. Volkov, Synchronizing automata and the Černý conjecture, in Language and Automata Theory and Applications (LATA 2008), LNCS 5196, 11–27.
3. Y. Shitov, An improvement to a recent upper bound for synchronizing words of finite automata, J. Autom. Lang. Comb. 24 (2019), 367–373.
4. Y. Zhu, The Černý conjecture for one-cluster automata via annular spectral descent, arXiv:2607.19675 (2026).

Source

Imported from Formal Conjectures Wikipedia/CernyConjecture, curated by Google DeepMind and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.