Le problème de la synchronisation et la conjecture de Cerný

Jean-Éric Pin

PostScript gzipped file, PDF file

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.

PostScript gzipped file, PDF file


Valid HTML 4.01!