  A word w of letters on edges of underlying graph Gamma of deterministic
finite automaton (DFA) is called the synchronizing word if w sends all states
of the automaton to a unique state. 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. This
simple looking conjecture is arguably the most fascinating and longstanding
open problem in the theory of finite automaton. The hypothesis was formulated
in 1966 by Starke. The problem has motivated great and constantly growing
number of investigations and generalizations. To prove the conjecture, we use
algebra with non-standard operations on a special class of matrices (row
monomial), 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 u and dimension of the space generated by
solutions Lx of matrix equation MuLx =Ms for synchronizing word s, as well as
on the relation between ranks of Mu and Lx.
