Some Aspects of Synchronization of DFA

A word w is called synchronizing (recurrent, reset, directable) word of deterministic finite automata (DFA) if w brings all states of the automaton to a unique state. According to the famous conjecture of erny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most (n–1)2. The problem is still open. It will be proved that the erny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state (n > 2) synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than (n–1)2/2. The last important class of DFA involved and studied by Sch tzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See .