Sur les mots synchronisants dans un automate fini

Jean-Éric Pin



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)2n 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.



Valid HTML 4.01!