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 Schuǔtzenberger 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/～trakht/syn.html.
展开▼
