Utilisation de l'algèbre linéaire en théorie des automates.

Jean-Éric Pin



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.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!