Slowly synchronizing automata with fixed alphabet size

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)², and he gave a sequence of DFAs reaching this bound. In this paper, we investigate the role of the alphabet size. For each possible alphabet size, we count DFAs on n≤6 states which synchronize in (n−1)²−e steps, for all e<2⌈n/2⌉. Furthermore, we give constructions of automata with any number of states, and 3, 4, or 5 symbols, which synchronize slowly, namely in n²−3n+O(1) steps. In addition, our results prove Černý's conjecture for n≤6. Our computations lead to 31 DFAs on 3, 4, 5 or 6 states, which synchronize in (n−1)² steps. Of these DFA's, 19 are new. The remaining 12, which were already known, are exactly the minimal ones. The 19 new DFAs are extensions of automata which were already known. But for n>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)².