Sur un cas particulier de la conjecture de Cerný

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, alors il existe un tel mot de longueur ≤ (n-1)2n est le nombre d'états de A. Nous proposons la généralisation suivante de cette conjecture: s'il existe un mot de rang ≤ k dans A, il existe un tel mot de longueur ≤ (n-k)2. Dans cet article, nous considérons des automates dans lesquels une lettre induit une permutation circulaire et nous montrons les résultats suivants:
(1) la seconde conjecture est vraie pour (n-1)/2 ≤ k ≤ n,
(2) si n est premier, la première conjecture est vraie,
(3) si n est premier et s'il existe une lettre de rang n - 1, la seconde conjecture est vraie.


Abstract : Let A be a finite automaton. We are concerned with the minimal length of the words that send all states on 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. As a generalization, we conjecture that, if there exists a word of rank ≤ k in A, there exists such a word with length ≤ (n-k)2. In this paper we deal only with automata in which a letter induces a circular permutation and prove the following results:
(1) the second conjecture is true for (n-1)/2 ≤ k ≤ n,
(2) if n is prime, the first conjecture is true,
(3) if n is prime and if there exists a letter of rank n - 1, the second conjecture is true.


PostScript gzipped file, PDF file

Valid HTML 4.01!