**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 (n ^{3}-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

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.

A package TESTAS for checking some kinds of 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.