A word w is called synchronizing (magic, recurrent, reset, directable) word of an automaton if w sends all states of the automaton on an unique state.
Jan Cerny had found in 1964 n-state complete DFA with shortest synchronizing word of length (n-1)2. The Cerny conjecture states that it is an upper bound for the length of the shortest synchronizing word for any n-state automaton.
Lower bound (n-1)2 Cerny 1964,
Upper bound (n3-n)/6 : Frankl, 1982, Kljachko, Rystsov, Spivak, 1987
An effective semigroup algorithm, mostly quadratic found all examples on the Cerny border for n<11, q<3 and n<8, q<5 (q - alphabet size)
The set of n-state complete DFA (n>2) with minimal reset word of length (n-1)2 contains only the sequence of Cerny and the eight automata mentioned above, 15 of size 3, 15 of size 4, one of size 5 and one of size 6.
A synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word.
The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of lengths of all its cycles is one. The problem was posed by Adler, Goodwyn and Weiss in 1970 and evoked noticeable interest among the specialists in the theory of graphs, deterministic automata, coding and symbolic dynamics.
The road coloring problem is important in automata theory: a synchronizing coloring makes the behavior of an automaton resistant against input errors since, after detection of an error, a synchronizing word can reset the automaton back to its original state, as if no error had occurred. The problem appeared first in the context of symbolic dynamics. Together with the Cerny conjecture the road coloring problem was belong to the most fascinating and longstanding problems in the theory of finite automata. The problem was discussed in "Wikipedia" - the popular Internet Encyclopedia. However, at the same time it proved to be hard and was considered in some papers as a "notorious open problem".
The recent positive solution of the road coloring conjecture (Trahtman, 2007) has posed a lot of generalizations and new problems.
Power Point Report of the proof on road coloring
A subquadratic algorithm of the road coloring was implemented in the package TESTAS. The program changed the labels (colors) on edges of the automaton for to turn it into synchronizing automaton. The input automaton must be deterministic (no empty cells in input). The search (input) table is considered as an automaton with an arbitrary coloring (sometimes even synchronizing). One can see a visual presentation of the graph of the automaton.
A high-speed linear algorithm of the visualization of the graph. Labels on arcs are presented by colors of the arcs. Strongly connected components, cycles and paths are seen on the layout.
1-st line length=22 for n=6, 4 colors length=31 for n=7, 3 colors length=74 for n=10, 2 colors
2-nd line length=30 for n=7, 4 colors length=42 for n=8, 3 colors length=92 for n=11, 2 colors
Download TESTAS (zip file, about 200 KB), the freeware version of the package TESTAS for checking some kinds of testability, finding synchronizing words and road coloring for WINDOWS.
The package includes three main programs. They
1) analyze an automaton of
the language presented as oriented labeled graph;
2) find syntactic semigroup of the language,
3) find road coloring of directed complete graph,
4) view visual image of the graph (and its subgraphs),
5) check the synchronizabity, find synchronizing words.