Matrix approach to synchronizing automata
A. N. Trahtman · arXiv (Cornell University) · 2019
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. J. Černy 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 Černy conjecture, claims that $(n-1)^2$ is a precise upper bound on the length of such a word over alphabet $Σ$ of letters on edges of $Γ$ for every complete $n$-state DFA. The hypothesis was formulated distinctly in 1966 by Starke. A special classes of matrices induced by words in the alphabet of labels on edges of the underlying graph of DFA are used for the study of synchronizing automata.