Synchronizing word

From Wikipedia, the free encyclopedia

In the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA which sends any state of the DFA to one and the same state.[1]

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 1964 Jan Černý conjectured that (n − 1)2 is the upper bound for the length of the shortest synchronizing word for any n-state complete DFA (a DFA with complete state transition graph).[1][2] If this is true, it would be tight, as there exist automata for which the shortest reset words have this length. The best upper bound known is (n3 − n)/6,[1], far from the lower bound.

For an n-state monotonic DFA over a k-letter input alphabet an algorithm by David Eppstein finds a synchronizing word in O(n3+n2k) time and O(n2) space; for this subclass of automata, an upper bound of (n − 1)2 on the length of a synchronizing word can be proven.[3] This article also proves that finding the minimum length reset sequence is an NP-complete problem.

[edit] References

  1. ^ a b c "Synchronization Algorithms and Cerny Conjecture"
  2. ^ Černý, J. (1964), “Poznámka k homogénnym eksperimentom s konecnými automatami”, Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14: 208–216  (in Slovak).
  3. ^ Eppstein, David (1990). "Reset Sequences for Monotonic Automata". SIAM Journal on Computing 19: 500–510. 

[edit] Further reading

  • Rystsov, I. C. (2004), “Černý's conjecture: retrospects and prospects”, Proc. Worksh. Synchronizing Automata, Turku (WSA 2004) .