Informatik-Kolloquium/MOVES-Seminar, 11. Dec 2007, 16:00, Seminarraum Info 10, Raum H 2010
Synchronizing automata preserving a chain of partial orders
Prof. Dr. Mikhail Volkov
Ural State University, Ekaterinburg, Russia
Abstract:
A deterministic finite automaton A is called synchronizing if there exists a word w whose action resets A, that is to leave the automaton in one particular state no matter which state it starts at. Any such word w is said to be a synchronizing word.
In 1964 Jan Černư constructed for each n>1 a synchronizing automaton with n states which shortest synchronizing word has length (n−1)2. Soon after that he conjectured that those automata represent the worst possible case, that is, every synchronizing automaton with n states can be reset by a word of length (n−1)2. By now this simply looking conjecture is arguably the most longstanding open problem in the combinatorial theory of finite automata.
Recently Avraham Trahtman confirmed the Černư conjecture for aperiodic (counter-free )automata. We present a new class of automata which strictly contains the class of aperiodic automata and shares with the latter certain synchronization properties. In particular, every strongly connected automaton in this new class is synchronizing and has a synchronizing word of length ⌊n(n+1)/6⌋ where n is the number of states of the automaton. The latter bound is new even for the aperiodic case.
In 1964 Jan Černư constructed for each n>1 a synchronizing automaton with n states which shortest synchronizing word has length (n−1)2. Soon after that he conjectured that those automata represent the worst possible case, that is, every synchronizing automaton with n states can be reset by a word of length (n−1)2. By now this simply looking conjecture is arguably the most longstanding open problem in the combinatorial theory of finite automata.
Recently Avraham Trahtman confirmed the Černư conjecture for aperiodic (counter-free )automata. We present a new class of automata which strictly contains the class of aperiodic automata and shares with the latter certain synchronization properties. In particular, every strongly connected automaton in this new class is synchronizing and has a synchronizing word of length ⌊n(n+1)/6⌋ where n is the number of states of the automaton. The latter bound is new even for the aperiodic case.
