Résumé : Nous utilisons des techniques
d'algèbre linéaire pour étudier le problème de
la synchronisation en théorie des automates. Soit A = (Q, X)
un automate fini. Chaque mot m de X* definit une
application de Q dans Q; le rang de m dans
A est l'entier Card {qm | q in Q }. Un mot de rang
1 envoie tous les états sur un seul état. Un tel mot
est appelé synchronisant (si un tel mot existe, on dit que
l'automate est synchronisant). Soit A un automate
synchronisant à n états. Notre résultat
principal affirme que s'il existe une lettre de rang ≤ 1 +
log2 n dans A, alors il existe un mot synchronisant
de rang ≤ (n-1)2.
Abstract : Techniques from linear algebra are used to study the
synchronization problem in automata theory. Let A = (Q, X) be a
finite automaton. Each word m in X* defines a map
from Q to Q; the rank of m in A is the
integer Card {qm | q in Q }. A word of rank 1 maps all
states onto a unique state. Such a word is called a synchronizing word (if
such a word exists the automaton itself is called a synchronizing
automaton). Let A be a synchronizing automaton with n states.
Our main result asserts that if there is a letter of rank ≤ 1 +
log2 n in A, then there exists a synchronizing word
of rank ≤ (n-1)2.