The Černý synchronizing-automaton conjecture
Let $\mathcal{A} = (Q, \Sigma, \delta)$ be a complete deterministic finite automaton with $n$ states over a finite nonempty alphabet $\Sigma$, with the transition map $\delta \colon Q \times \Sigma \to Q$ extended to words letter by letter. A word $w \in \Sigma^*$ is a reset word if $\delta(q, w)$ is the same state for every $q \in Q$, and $\mathcal{A}$ is synchronizing if it has one; its length counts letters, and the empty word has length $0$. Černý constructed, for every $n \ge 2$, a synchronizing automaton with $n$ states and two letters whose shortest reset word has length $(n-1)^2$. Combining results of Pin and Frankl, every synchronizing automaton with $n$ states has a reset word of length at most $(n^3 - n)/6$; Szykuła improved the leading constant, and Shitov improved it further to $\frac{7}{48} + \frac{15625}{798768}$. Eppstein proved the bound $(n-1)^2$ for orientable (in his terms, monotonic) automata, and Kari proved the bound $n^2 - 3n + 3$ for Eulerian automata.
Problem. Does every synchronizing complete deterministic finite automaton with $n$ states have a reset word of length at most $(n-1)^2$, for every $n \ge 1$ and every finite alphabet, with no further restriction on the automaton?
Source: Černý, in his talk at the Bratislava Cybernetics Conference (1969), after his series of automata (1964); first in print in Černý, Pirická and Rosenauerová (1971). See Volkov (2008).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- GR
- Keywords
- AIM Open Applied Problems, Černý conjecture, reset words, synchronizing automata
References
@article{cerny1964,
author = {{\v{C}}ern{\'y}, J{\'a}n},
title = {Pozn{\'a}mka k homog{\'e}nnym experimentom s kone{\v{c}}n{\'y}mi automatmi},
journal = {Matematicko-fyzik{\'a}lny {\v{c}}asopis Slovenskej akad{\'e}mie vied},
volume = {14},
number = {3},
year = {1964},
pages = {208--216},
note = {In Slovak; English translation: A note on homogeneous experiments with finite automata, J. Autom. Lang. Comb. 24 (2019), no. 2--4, 123--132, doi:10.25596/jalc-2019-123},
}
@article{cerny1971,
author = {{\v{C}}ern{\'y}, J{\'a}n and Pirick{\'a}, Alica and Rosenauerov{\'a}, Blanka},
title = {On directable automata},
journal = {Kybernetika},
volume = {7},
number = {4},
year = {1971},
pages = {289--298},
}
@inproceedings{volkov2008,
author = {Volkov, Mikhail V.},
title = {Synchronizing automata and the {\v{C}}ern{\'y} conjecture},
booktitle = {Language and Automata Theory and Applications (LATA 2008)},
series = {Lecture Notes in Comput. Sci.},
volume = {5196},
publisher = {Springer},
address = {Berlin},
year = {2008},
pages = {11--27},
doi = {10.1007/978-3-540-88282-4_4},
}
@incollection{pin1983,
author = {Pin, Jean-{\'E}ric},
title = {On two combinatorial problems arising from automata theory},
booktitle = {Combinatorial Mathematics (Marseille-Luminy, 1981)},
series = {North-Holland Math. Stud.},
volume = {75},
publisher = {North-Holland},
address = {Amsterdam},
year = {1983},
pages = {535--548},
doi = {10.1016/S0304-0208(08)73432-7},
note = {Also Ann. Discrete Math. 17},
}
@article{frankl1982,
author = {Frankl, P{\'e}ter},
title = {An extremal problem for two families of sets},
journal = {European J. Combin.},
volume = {3},
number = {2},
year = {1982},
pages = {125--127},
doi = {10.1016/S0195-6698(82)80025-5},
}
@inproceedings{szykula2018,
author = {Szyku{\l}a, Marek},
title = {Improving the upper bound on the length of the shortest reset word},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
series = {LIPIcs},
volume = {96},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2018},
pages = {56:1--56:13},
doi = {10.4230/LIPIcs.STACS.2018.56},
eprint = {1702.05455},
archivePrefix = {arXiv},
}
@article{shitov2019,
author = {Shitov, Yaroslav},
title = {An improvement to a recent upper bound for synchronizing words of finite automata},
journal = {J. Autom. Lang. Comb.},
volume = {24},
number = {2--4},
year = {2019},
pages = {367--373},
doi = {10.25596/jalc-2019-367},
}
@article{eppstein1990,
author = {Eppstein, David},
title = {Reset sequences for monotonic automata},
journal = {SIAM J. Comput.},
volume = {19},
number = {3},
year = {1990},
pages = {500--510},
doi = {10.1137/0219033},
}
@article{kari2003,
author = {Kari, Jarkko},
title = {Synchronizing finite automata on {E}ulerian digraphs},
journal = {Theoret. Comput. Sci.},
volume = {295},
number = {1-3},
year = {2003},
pages = {223--232},
doi = {10.1016/S0304-3975(02)00405-X},
}
@misc{volkov2026list,
author = {Volkov, Mikhail V.},
title = {List of results on the {\v{C}}ern{\'y} conjecture and reset thresholds for synchronizing automata},
year = {2026},
eprint = {2508.15655},
archivePrefix = {arXiv},
note = {Version 4, 13 January 2026},
}
@misc{aim-cerny,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The Černý synchronizing-automaton conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/291-cerny.md},
note = {Entry 291 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00507, "The Černý synchronizing-automaton conjecture", clopen.solutions.