A. N. Trahtman. Notable trends concerning the synchronization of graphs and automata
Natural Sciences / Computer Science / Automata theory
Submitted on: Apr 01, 2012, 21:05:16
Description: A word w is called synchronizing (recurrent, reset, directed) word of a deterministic finite automaton (DFA) if w sends all states of the automaton on a unique state. Jan Cerny had found in 1964 a sequence of n-state complete DFA with shortest synchronizing word of length (n-1)^2. He had conjectured that it is an upper bound for the length of the shortest synchronizing word for any n-state complete DFA. The examples of DFA with shortest synchronizing word of length (n-1)^2 are relatively rare. To the Cerny sequence were added in all examples of Cerny, Piricka and Rosenauerova (1971), of Kari (2001) and of Roman (2004). By help of a program based on some effective algorithms, a wide class of automata of size less than 11 was checked.