Synchronizing word

Source: Wikipedia, the free encyclopedia.
For synchronizing words in the theory of synchronized codes, see Self-synchronizing code § Synchronizing word.
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 (as is the word red-red-red-blue-red-red-blue-red-red); the word blue-blue-red-blue-blue-red-blue-blue-red is another synchronizing word that sends all states to the green state.

In

deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state.[1]
That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. Not every DFA has a synchronizing word; for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized.

Existence

Given a DFA, the problem of determining if it has a synchronizing word can be solved in

exponential
in the number of states. A polynomial algorithm results however, due to a theorem of Černý that exploits the substructure of the problem, and shows that a synchronizing word exists if and only if every pair of states has a synchronizing word.

Length

Unsolved problem in computer science
If a DFA with states has a synchronizing word, must it have one of length at most ?
More unsolved problems in computer science

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. In 1969,

upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph).[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.[4] The best upper bound known is 0.1654n3, far from the lower bound.[5]
For n-state DFAs over a k-letter input alphabet, an algorithm by
NP-complete. 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.[2]

Road coloring

The

strongly connected and aperiodic regular digraph can be labeled in this way; their conjecture was proven in 2007 by Avraham Trahtman.[6][7]

Related: transformation semigroups

A transformation semigroup is synchronizing if it contains an element of rank 1, that is, an element whose image is of cardinality 1.[8] A DFA corresponds to a transformation semigroup with a distinguished generator set.

References

  1. ^ Avraham Trakhtman: Synchronizing automata, algorithms, Cerny Conjecture. Accessed May 15, 2010.
  2. ^
    doi:10.1137/0219033
    .
  3. ISBN 978-3-540-88281-7
    ; see in particular p. 19
  4. ^ Černý, Ján (1964), "Poznámka k homogénnym experimentom s konečnými automatmi" (PDF), Matematicko-fyzikálny časopis Slovenskej Akadémie Vied, 14: 208–216 (in Slovak).
  5. MR 4023068
  6. ^ Adler, R. L.; Weiss, B. (1970), "Similarity of automorphisms of the torus", Memoirs of the American Mathematical Society, 98.
  7. MR 2534238
  8. ^ Cameron, Peter (2013), Permutation groups and transformation semigroups (PDF).

Further reading

Retrieved from "https://en.wikipedia.org/w/index.php?title=Synchronizing_word&oldid=1285525547"