Résumé : Soit A un automate fini. On
s'intéresse à la longueur minimale des mots qui envoient tous
les états sur un seul état (mots synchronisants). J.
Cerný a conjecturé que, s'il existe un mot synchronisant dans
A alorts il existe un tel mot de longueur ≤
(n-1)2 où n est le nombre d'états de
A. Le but de cet article est de présenter divers
résultats sur cette conjecture, de donner une approche
générale du problème et de donner une solution
complète dans un cas spécial.
Abstract : Let A be a finite automaton. We are
concerned with the minimal length of the words that send all states to a
unique state (synchronizing words). J. Cerný has conjectured that,
if there exists a synchronizing word in A then there exists
such a word with length ≤ (n-1)2 where n is the
number of states of A. The aim of this paper is to present
some results about this conjecture, to indicate a generalized approach of
the problem and to give a complete solution for a special case.