Some new Features of Row Monomial Matrices for the Study of DFA | Chapter 10 | Recent Recent Advances in Mathematical Research and Computer Science Vol. 9

 The work presents some new results and ideas concerning the synchronization of automata.

A word w of letters on edges of underlying graph Γ of deterministic finite automaton (DFA) is called synchronizing if w 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 u and dimension of the space generated by solutions L_x of matrix equation M_u L_x= M_s for synchronizing word s, as well as on the relation between ranks of M_u and L_x.

Author(S) Details

A. N. Trahtman
Department of Mathematics, Bar-Ilan University, 52900, Ramat Gan, Israel.

View Book:- https://stm.bookpi.org/RAMRCS-V9/article/view/6028