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 Cerny 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 ( ern 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 Schutzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established. See http://www.cs.biu.ac.il/similar to trakht/syn.html.
synchronization deterministic finite automata (dfa) aperiodic semigroup cerny conjecture