For every synchronizing deterministic finite automaton A=(Q,Sigma,delta) with |Q|=n, there exists a word w∈Sigma^ and a state q_0∈ Q such that delta(q,w)=q_0 for every q∈ Q and |w|≤ (n-1)^2.

Černý’s conjecture

Posed by Černý in 1964, the conjecture says that every synchronizing automaton with $n$ states has a reset word of length at most $(n-1)^2$ . The matching lower bound is attained by Černý’s automata, but the general upper bound remains unknown.

Known results

Aperiodic automata: bound $n(n-1)/2$ (2007); Volkov improved this to $n(n+1)/6$ for strongly connected cases.
Eulerian synchronizing automata: bound $n^2-3n+3$ .
$1$ -extensible and one-cluster synchronizing automata satisfy the conjecture.
The best general upper bound is cubic, due to Shitov: $\mathfrak{C}(n)\leq\left(\frac{7}{48}+\frac{15625}{798768}\right)n^3+o(n^3)$ ; no quadratic general bound is known.

August 2026 survey

A new survey consolidates open problems and auxiliary results but reports no proof or refutation. Earlier claimed proofs by Trahtman were undermined by his February 10, 2024 acknowledgment of an error; the latest survey continues to classify the conjecture as open.

Current status (as of August 2026): Černý’s conjecture remains open; the quadratic bound is proved for several restricted classes, while the general problem has only a cubic upper bound and no known counterexample.

Černý’s conjecture

Primary source

Additional references

Progress summary

Solutions 0