Some Aspects of Synchronization of DFA

A word w is called synchronizing (recurrent, reset, directable) wordof deterministic finite automata (DFA) if w brings all states of theautomaton to a unique state. According to the famous conjecture ofCerny from 1964, every n-state synchronizing automaton possessesa synchronizing word of length at most (n-1)^2. The problem is still open.It will be proved that the Cerny conjecture holds good forsynchronizing DFA with transition monoid having no involutions andfor every n-state (n>2) synchronizing DFA with transition monoidhaving only trivial subgroups the minimal length of synchronizing wordis not greater than (n-1)^2/2. The last important class of DFAinvolved and studied by Schutzenberger is called \it aperiodic;its automata accept precisely star-free languages. Some properties of anarbitrary synchronizing DFA were established. Seehttp://www.cs.biu.ac.il/˜trakht/syn.html.