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. |