Černý's conjecture for synchronizing DFAs

Let M=(Q,Σ,δ)M=(Q,\Sigma,\delta) be a deterministic finite automaton, and let n=Qn=|Q| be its order. A word is synchronizing if it maps every state of QQ to the same state.

Černý's conjecture. If MM is synchronizable, then MM has a synchronizing word of length at most

(n1)2.(n-1)^2.

Černý constructed, for every nn, an nn-state DFA whose shortest synchronizing word has exactly this length, so the conjecture asserts that his examples are extremal. It remains a central open question in automata theory.

Sources & referencesView supporting material

Primary source

Peter Bradshaw, Alexander Clow and Ladislav Stacho, “A cornering strategy for synchronizing a DFA”, arXiv:2405.00826 (2025).

Additional references

9 papers in this index state this conjecture (2008–2024). The statement above is taken from the most recent of them; the others are arXiv:2008.12166, arXiv:1906.02602, arXiv:1810.11323, arXiv:1704.04047, arXiv:1511.03184, arXiv:1306.0729, arXiv:1005.1835, arXiv:0808.1429.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.