We give a survey on the following problem (known as the synchronization problem). Let A = (Q, X) be a finite automaton. Every word m in X* defines a function from Q into Q; the rank of m in A is the integer Card {qm ¦ q in Q }. A word of rank 1 maps all the states onto a single state and is called a synchronizing word (if such a word exists, the automaton itself is called synchronizing). Let A an automaton with n states. Cerný has conjectured that if A is synchronizing, then there exists a synchronizing word of length ≤ (n-1)^2. A generalization of this conjecture states that if there exists a word of rank ≤ k in A, then there exists such a word of length ≤ (n-k)^2.
@article{hal-00340776,
author = {Pin, Jean-Eric},
title = {Le probl\`eme de la synchronisation et la conjecture de Cern\'y},
journal = {HAL},
volume = {1981},
number = {0},
year = {1981},
language = {fr},
url = {http://dml.mathdoc.fr/item/hal-00340776}
}
Pin, Jean-Eric. Le problème de la synchronisation et la conjecture de Cerný. HAL, Tome 1981 (1981) no. 0, . http://gdmltest.u-ga.fr/item/hal-00340776/