Slowly synchronizing automata with fixed alphabet size
Michiel de Bondt, Henk Don, Hans Zantema · arXiv (Cornell University) · 2016
It was conjectured by Černý in 1964 that a synchronizing DFA on $n$ states always has a shortest synchronizing word of length at most $(n-1)^2$, and he gave a sequence of DFAs for which this bound is reached. In this paper, we investigate the role of the alphabet size. For each possible alphabet size, we count DFAs on $n \le 6$ states which synchronize in $(n-1)^2 - e$ steps, for all $e 3$, we prove that the Černý automaton on $n$ states does not admit non-trivial extensions with the same smallest synchronizing word length $(n-1)^2$.