The Černý conjecture for one-cluster automata with prime length cycle (Q719288)

A deterministic finite automaton \(M\) is said to be synchronizing if there is a ``reset word'' \(w\) such that any path from the initial state labeled \(w\) leads to the same state. A celebrated conjecture of \textit{J. Černý} [Mat.-Fyz. Čas., Slovensk. Akad. Vied 14, 208--216 (1964; Zbl 0137.01101)] states that if an \(n\)-state automaton is synchronizing, then there is a reset word of length at most \((n-1)^2\). An automaton is said to be one-cluster if there exists an input letter such that the edges corresponding to \(a\) contain exactly one simple cycle. In this paper the author, using techniques of linear algebra, proves Černý's conjecture in the special case of ``one-cluster automata'' with prime length cycle.