Riassunto : Noi diamo una panoramica sul seguende problema (detto il
problema della sincronizzazione). Sia A = (Q, X) un
automa finito. Ogni parola m in X* definisce una
funzione da Q in Q; il rango di m in
A è l'intero Card {qm ¦ q in Q }. Una
parola di rango 1 associa a tutti gli stati un unico stato ed è
detta una parola sincronizzante (se una tale parola esiste l'automa
stesso è detto sincronizzante). Sia A un automa
con n stati. Cerný ha fatto la congettura che se A
è sincronizzante, allora esiste una parola sincronizzante di
lunghezza ≤ (n-1)2. Una generalizzazione di questa
congettura è che se esiste una parola di rango ≤ k in
A, allora esiste una parola cosifatta di lunghezza
≤ (n-k)2.
Résumé : Nous donnons un exposé de
synthèse sur le problème suivant (appelé
problème de la synchronisation). Soit A = (Q,
X) un automate fini. Chaque mot m de X*
definit une fonction de Q dans Q; le rang de m
dans A est l'entier Card {qm ¦ q in Q }. Un mot
de rang 1 associe à tout état un unique état et est
appelé un mot synchronisant (si un tel mot existe, l'automate
lui-même est appelé synchronisant). Soit
A un automate à n états. Cerný a
conjecturé que si A est synchronisant, alors il existe
un mot synchronisant de longueur ≤ (n-1)2. Une
généralisation de cette conjecture affirme que s'il existe un
mot de rang ≤ k dans A, alors il existe un tel
mot de longueur ≤ (n-k)2.
Abstract : 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.