A finite automaton is synchronizing if it permits a reset word, i.e. if there exists a sequence of transitions which maps any state to a predetermined fixed state. In this work we define a hierarchy of permutation group properties related to synchronization, and consider the links between them. Referencing the O’Nan-Scott classification of primitive groups, we prove that all synchronizing groups, which are not almost simple, are also separating. Additionally, we establish an upper bound for the length of the shortest reset word in an automaton whose invertible transitions form a spreading group, and use this bound to prove Pin’s theorem concerning the reset words of automata with a prime number of states and a cyclic transition.
|
