Date: Sunday, 20 Iyar 5765 (May 29, '05)

Speaker: Dr. Avraham Trakhtman (Bar-Ilan University)

Title: "Two aspects of synchronization of finite automata"

Abstract:
---------
A word w is called synchronizing (recurrent, reset) if w sends all states
of an automaton to a unique state. Cerny had conjectured in 1964 that for
deterministic n-state complete automata the existence of a synchronizing
word implies existence of such a word of length not greater than (n-1)^2.
The synchronization 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.

A problem with a long history is the estimation of the minimal length of a
synchronizing word. Best known as the Cerny conjecture, it was stated
independently by distinct authors. Jan Cerny had found in 1964 an n-state
complete DFA with shortest synchronizing word of length (n-1)^2. He had
conjectured that it is an upper bound for the length of the shortest
synchronizing word for any n-state complete DFA. The best known upper
bound is currently (n^3-n)/6. The conjecture was verified for many classes
of automata, but in general the problem remains open.

The testing of synchronizing automata is an indispensable part of
investigation in this area. The best algorithm so far (due to Eppstein)
finds a synchronizing word for an n-state DFA in n^3 time.

We improve the time complexity and reduce it to n^2 for a wide class of
automata having a synchronizing word of length not greater than quadratic.

No examples of automata are known for which the length of the shortest
synchronizing word is greater than (n-1)^2. The length of the
synchronizing word found by the algorithm was not greater than n^2 in all
cases considered to date, including all exotic examples. Therefore we can
consider the algorithm as conditionally or almost quadratic. The algorithm
is implemented in our package TESTAS.

The existence of some non-trivial subgroup in the transition semigroup of
the automaton is essential in many investigations. An opposite approach
confirms the conjecture for automata having a syntactic semigroup without
non-trivial subgroups. Expanding this approach, we establish that a
synchronizing DFA has a synchronizing word of length not greater than
n(n-1)/2 for automata with syntactic semigroup having no subgroups of
order two and therefore the Cerny conjecture holds true for such DFA.