Černý's conjecture for synchronizing DFAs
Černý's conjecture for synchronizing DFAs
Let be a deterministic finite automaton, and let be its order. A word is synchronizing if it maps every state of to the same state.
Černý's conjecture. If is synchronizable, then has a synchronizing word of length at most
Černý constructed, for every , an -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.