Le problème de la synchronisation et la conjecture de Cerny.

Le problème de la synchronisation et la conjecture de Cerny

Thèse de troisième cycle, Jean-Éric Pin

Résumé : Soit A = (Q, X) un automate fini. Chaque mot m de X^* definit une application q --> qm 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 et est appelé mot synchronisant. Si un tel mot existe, on dit que l'automate est synchronisant dans A. La conjecture de Cerny affirme que si un automate à n états est synchronisant, alors il admet un mot synchronisant de longueur ≤ (n-1)². Nous proposons dans cette thèse la généralisation suivante de cette conjecture: si dans un automate à n états, il existe un mot de rang ≤ n-k, alors il existe un tel mot de rang ≤ k²: la conjecture de Cerny correspond au cas k = n-1. Cette thèse fournit un certain nombre de résultats partiels en direction de ces deux conjectures. Cerny avait déjà montré que la borne inférieure (n-1)²était atteinte. Nous obtenons une borne supérieure en (1/2 - π²/36)n³ + o(n³). Nous prouvons la conjecture généralisée pour k = 1, 2 et 3 (le cas k = 3 nécessite une analyse combinatoire assez détaillée) et nous montrons que la borne inférieure k² est effectivement atteinte. Nous obtenons également une borne supérieure en (1/3)k³ - k² + (14/3)k - 5. Ce résultat est basé sur une technique d'analyse descendante que l'on peut sans doute améliorer, mais qui donnera au mieux une borne en (1/6)k³. Nous résolvons par ailleurs les conjectures dans divers cas particuliers. Nous montrons par exemple que la conjecture de Cerny est vraie s'il existe une lettre de rang ≤ (1 + log_2 n). Nous prouvons également les deux conjectures pour certains automates "circulaires" (automates dans lesquels une lettre induit une permutation circulaire sur l'ensemble des états) et pour les automates triangulables (automates dans lesquels les matrices associées aux lettres sont simultanément triangulables).

Abstract : Let A = (Q, X) be a deterministic automaton. Each word m of X^* defines a map q --> qm 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 to a single state and is called a synchronizing word in A. If such a word exists, the automaton is said to be synchronizing. Cerny's conjecture states that if an n-state automaton is synchronizing, there exists a synchronizing word of length ≤ (n-1)². In this thesis, we propose the following generalization of Cerny's conjecture: if an n-state automaton admits a word of rank ≤ n-k, then there exists such a word of length ≤ k²: Cerny's conjecture corresponds to the case k = n-1. In this thesis, we give some partial results on both conjectures. Cerny had already proved that the lower bound (n-1)² can be reached. We obtain an upper bound of the form (1/2 - π²/36)n³ + o(n³). We also prove the generalized conjecture for k = 1, 2 and 3 (the case k = 3 already requires some detailed combinational analysis) and we show that the lower bound k² can effectively be reached. We also obtain the upper bound (1/3)k³ - k² + (14/3)k - 5. This result is based on a technique of descending analysis which can probably be improved, but will give at best a (1/6)k³ bound. We also solve both conjectures in various particular cases. For instance, we show that Cerny's conjecture is true if there exists a letter of rank ≤ (1 + log_2 n). We also show that both conjectures are true for certain circular automata (automata in which some letter induces a circular permutation on the set of states) and for the triangulable automata (automata for which the matrices associated with the lettres are simultaneously triangulable).