Synchronization
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.
Cerny problem:
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.
Now
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)
Conjecture
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.
Road coloring:
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.
Visualisation
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
Testability
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.