Theoretical review surveys open problems surrounding the Černý conjecture in finite automata, highlighting key linear-algebraic techniques and computational complexity challenges.
We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture.A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state.The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n -1) 2 .We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods.Some new auxiliary results are also presented.
No takes yet. Share an insight, caveat, or question.
Marek Szykuła (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: