Some new Features of Row Monomial Matrices for the Study of DFA

Abstract

The work presents some new results and ideas concerning the synchronization of automata.
A word \(W\) of letters on edges of underlying graph \(\Gamma\) of deterministic finite automaton (DFA) is called synchronizing if  sends all states of the automaton to a unique state. The problem is decide whether or not deterministic finite automaton (DFA) is synchronizing, find relatively short synchronizing words and such a word of minimal length.
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. The hypothesis was formulated in 1966 by Starke.
To prove the conjecture, we use algebra of a special class of row monomial matrices (one unit and rest zeros in every row), induced by words in the alphabet of labels on edges. These matrices generate a space with respect to the mentioned operation.
The proof is based on connection between length of words  and dimension of the space generated by solutions \(L_x\) of matrix equation \(M_uL_x=M_s\)  for synchronizing word \(s\), as well as on the relation between ranks of \(M_u\) and \(L_x\).