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.
Graphs with maximal length of synchronizing word (n-1)2. Cerny for n states (here n=8) 2 colors; Kari: 6 states, 2
colors, Roman: 5 states, 2 colors; two found
by Testas: 4 states, 3 colors; Ceny_Piricka_Rozenaurova: 4 states, 2 colors; three found by Testas: 3 states, 3 and 2 colors
Near maximal length of synchronizing word
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
There is a deep connection between
problems in string pattern matching and finite automata. A number of classical
algorithms in everyday use in text editors actually compute finite automata
from descriptions of patterns as regular expressions. The class of languages
arising from here is the class of locally testable
languages and their generalizations.
The concept of local testability is connected with languages, finite
automata, graphs and semigroups.
Locally testable automata have a
wide spectrum of applications.
The package contains a set of
procedures for deciding whether or not a language given by transition graph or
by transition semigroup of its automaton is locally
testable, left [right] locally testable, threshold locally testable, bilateral
locally testable or piecewise testable .
The bounds for the order of local testability
of transition graph and order of local testability
of transition semigroup are also found.
The k-testability of transition graph is
verified for arbitrary k.
Strictly locally testable automata and their order
are checked.
The local idempotency
is verified on the transition graph of the automaton.
Synchronizability of transition graph of
automaton is verified and some synchronizing words of short (and of minimal)
length are found.
The syntactic semigroup is constructed from
the transition graph of the automaton. The complexity of the algorithms is
polynomial.
Some definitions
Local
testability, Threshold local testability
Left,
Right local testability
Piecewise
testability
Verification
Tools
Paper
in postscript file
A package TESTAS for
checking some kinds of testability.
TESTAS on several prominent CONFERENCES
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.