Synchronizing word

Given a DFA, the problem of determining if it has a synchronizing word can be solved in polynomial time[2] using a theorem due to Ján Černý.

The problem of estimating the length of synchronizing words has a long history and was posed independently by several authors, but it is commonly known as the Černý conjecture.

[3] If this is true, it would be tight: in his 1964 paper, Černý exhibited a class of automata (indexed by the number n of states) for which the shortest reset words have this length.

[5] For n-state DFAs over a k-letter input alphabet, an algorithm by David Eppstein finds a synchronizing word of length at most 11n3/48 + O(n2), and runs in time complexity O(n3+kn2).

However, for a special class of automata in which all state transitions preserve the cyclic order of the states, he describes a different algorithm with time O(kn2) that always finds the shortest synchronizing word, proves that these automata always have a synchronizing word of length at most (n − 1)2 (the bound given in Černý's conjecture), and exhibits examples of automata with this special form whose shortest synchronizing word has length exactly (n − 1)2.

This drawing represents a DFA with eight states and two input symbols, red and blue. The word blue-red-red-blue-red-red-blue-red-red is a synchronizing word that sends all states to the yellow state; the word blue-blue-red-blue-blue-red-blue-blue-red is another synchronizing word that sends all states to the green state.