The length of a minimal synchronizing word and the Černy conjecture
A. N. Trahtman · arXiv (Cornell University) · 2014
A word w of letters on edges of underlying graph Gamma of deterministic finite automaton (DFA) is called the synchronizing word if w sends all states of the automaton to a unique state. J. Cerny discovered in 1964 a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)^2. The hypothesis, well known today as the Cerny conjecture, claims that it is also precise upper bound on the length of such a word for a complete DFA. This simple-looking conjecture is arguably the most fascinating and longstanding open problem in the combinatorial theory of finite automata. An attempt to prove the Cerny conjecture is wrong.