An finite-state automaton is said to be synchronizing if it admits
a reset word. Cerny's conjecture, first formulated in 1964, states that
if an n-state automaton admits a reset word, then it admits such a word
with length at most (n-1)^2. The study of synchronizing automata led
to the exploration of several interesting problems in the theory of
finite permutation groups. A permutation group G acting on a finite set
is said to be non-synchronizing if there is a non-trivial partition P of
the underlying set and a transversal S of P such that the images of S
under the action of G are all transversals for P. Otherwise G is called
synchronising. It is clear that a synchronizing group is transitive and
it is primitive. However, the converse of this statement is not true:
there are several classes primitive non-synchronizing groups. In this
talk I will explain the connection between synchronizing groups and
automata, exhibit several classes of primitive non-synchronizing groups,
and report on some computer calculations that was aimed at determining
the primitive non-synchronising groups of degree up to 100. |