Semisimple synchronizing automata and the Wedderburn-Artin theory (Q5890812)

The article investigates the famous Černý conjecture, which states that every synchronizing automaton has a reset word of length at most \((n-1)^2\), where \(n\) is the number of states. A synchronizing automaton is a deterministic finite-state automaton for which there exists an input sequence that takes it into a fixed special state irrespective of the state that the automaton initially is in. Such a word is also called a reset word and the Černý conjecture postulates an upper bound on the length of a minimal-length reset word. The conjecture is still open and has been so for many years.NEWLINENEWLINEThe approach taken here employs rings and ideals to tackle the problem from a different direction. The radical ideal of a synchronizing automaton is defined and characterized, which leads to the notion of semisimple automata, for which the radical of the automaton factorized by its reset words is trivial. It is demonstrated that semisimple automata form a reasonably large class of automata and that they, in particular, include the automata discovered by Černý that establish the lower bound \((n-1)^2\). Moreover, it is demonstrated that for those automata a reset word can be obtained as a power of a radical word, which reduces the problem to finding short radical words. In a number of cases it is shown that this approach is successful, even though no improvements over the state of the art are obtained. The authors also postulate a weaker version of the conjecture, called the radical conjecture, which, if true, would imply a bound of \(2(n-1)^2\).NEWLINENEWLINEThe paper is well written but assumes a fair amount of linear algebra from the reader. Interested readers might want to study the general problem from the original papers to get some perspective on the results obtained in the present one. The paper relies on the Wedderburn-Artin theory from abstract algebra, but references to the relevant results are provided.