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.


 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.


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.


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                      



 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.