Mot synchronisant

Un automate fini sur deux lettres Modèle:Rouge et Modèle:Bleu. Le mot Modèle:BleuModèle:RougeModèle:RougeModèle:BleuModèle:RougeModèle:RougeModèle:BleuModèle:RougeModèle:Rouge est synchronisant et envoie tous les états sur l'état jaune ; le mot Modèle:BleuModèle:BleuModèle:RougeModèle:BleuModèle:BleuModèle:RougeModèle:BleuModèle:BleuModèle:Rouge aussi est synchronisant et envoie tous les états sur l'état vert.

En informatique théorique, et plus particulièrement en théorie des automates finis déterministes, un mot synchronisant, en anglais aussi reset word, est un mot sur l'alphabet d'entrée d'un automate qui envoie tout état de l'automate sur le même étatModèle:,. En d'autres termes, si un ensemble de copies de l'automate démarre, simultanément chacune en un état différent, elles se trouvent toutes après la lecture du mot synchronisant en même temps dans le même état. Les automates finis ne possèdent pas tous un mot synchronisant. Par exemple, un automate à deux états réduit à un circuit de longueur 2 ne peut pas être synchronisé. Le problème majeur encore ouvert concerne la longueur des plus courts mots synchronisants, et est connu sous le nom de conjecture de Černý.

Existence

Un automate non synchronisable (à gauche) et synchronisable (à droite).

Pour un automate fini déterministe donné, la question de l'existence d'un mot synchronisant peut être décidée en temps polynomial en utilisant un théorème dû à Černý décrit plus loin qui montre qu'un mot synchronisant existe si et seulement si toute paire d'états possède un mot synchronisant.

Un automate qui possède un mot synchronisant est parfois appelé synchronisé(en anglais synchronised automaton) ou synchronisable.

Conjecture de Černý

Le problème majeur, encore ouvert, concerne la longueur des plus courts mots synchronisants, et est connu sous le nom de conjecture de Černý. En 1964, le mathématicien Ján Černý conjecture que $(n-1{)}^2$ est un majorant de la longueur du plus court mot synchronisant dans un automate fini déterministe complet à $n$ étatsModèle:, : Modèle:Théorème La conjecture est encore ouverte ; dans son article de 1964, Ján Černý donne une classe d'automates, indexée par le nombre $n$ d'états, pour laquelle le plus court mot synchronisant est de longueur $(n-1{)}^2$ ; ce nombre est donc un minorant dans le cas général. D'autres familles ont été définies qui vérifient la conjecture. Le meilleur majorant général connu pendant longtemps a été $(n^3-n)/6$Modèle:,. Cette majoration est due à Jean-Éric Pin et Peter Frankl. Marek Szykuła annonce en 2017 une majoration légèrement meilleure : elle est $114n^3/685+O(n^2)$.

Paires synchronisables

La paire (1,4) du deuxième automate est synchronisable.

Étant donné un automate fini déterministe complet avec un ensemble $Q$ d'états, on note $Q\cdot w=\{q\cdot w\mid q\in Q\}$ et l’ensemble des états atteints à partir d'un état de $Q$ par le mot $w$. Le rang du mot $w$ est le nombre d'éléments de l'ensemble $Q\cdot w$. Un mot synchronisant est un mot de rang 1. Une paire d'états $(p,q)$ est synchronisable s'il existe un mot $w$ tel que $p\cdot w=q\cdot w$. L'énoncé de Černý annoncé plus haut est le suivant :

Un automate est synchronisable si et seulement si toute paire d'états est synchronisable.

La paire (1,4) du premier automate n'est pas synchronisable.

Pour tester si un automate fini déterministe complet à $n$ est synchronisable, on construit l'automate des paires, et on cherche s'il existe un chemin de toute paire à une paire dont les composantes sont identiques.

Algorithmes

Pour un automate à $n$ états sur un alphabet à $k$ lettres, David Eppstein donne un algorithme pour calculer une mot synchronisant de longueur au plus $11n^3/48+O(n^2)$ dont la complexité en temps est $O(n^3+k{n}^2)$. Cet algorithme ne donne pas toujours le mot synchronisant le plus court pour un automate donné ; Eppstein démontre d'ailleurs que le problème du calcul du plus court mot synchronisant est NP-complet. Il donne toutefois une classe d'automates pour lesquels un algorithme en temps $O(k{n}^2)$ fournit toujours un mot synchronisant de longueur au plus $(n-1{)}^2$ (la borne de Černý) et donne des automates de cette forme particulière pour lesquels le plus court mot synchronisant a exactement la longueur $(n-1{)}^2$.

Automates apériodiques

La recherche d'une réponse à la conjecture de Černý a conduit à examiner des automates particuliers, et parmi eux notamment les automates apériodiques : un automate est dit apériodique si son monoïde de transitions est apériodique ou si, de manière équivalente, il existe un entier $m$ tel que, pour tout état $q$ et pour tout mot $w$, on a :

$q\cdot w^m=q\cdot w^{m+1}$.

On peut noter qu'on a toujours $q\cdot w^m=q\cdot w^{m+r}$ pour un entier $r>0$ ; la particularité qui définit les automates apériodiques est que l'on peut choisir $r=1$. Pour les automates apériodiques, la conjecture de Černý est vérifiée grâce à la proposition suivante :

Cette borne a été améliorée par Volkov dans le cas particulier des automates apériodiques fortement connexes. Il montre que la borne peut être remplacée par $n(n+1)/6$ ; en fait, on ne connaît pas d'automates fortement connexe apériodique qui n'a pas de mot synchronisant de longueur au plus $n-1$.

Coloriage des routes

Modèle:Article détaillé Le coloriage des routes est le problème de colorer les arcs d'un graphe régulier orienté avec k symboles (où k est le degré sortant des sommets) de sorte de le transformer en un automate déterministe fini qui possède un mot synchronisant. Il a été conjecturé en 1970 par Benjamin Weiss et Roy Adler que tout graphe régulier fortement connexe et apériodique peut être coloré de manière à avoir cette propriété ; leur conjecture a été démontrée en 2007 par Avraham Trahtman.

Bibliographie

Avraham Trahtman donne, sur son site, une liste bibliographique détaillée sur la conjecture de Cerny, la coloration des routes et les mots synchronisants.

• Modèle:Ouvrage.
• Modèle:Chapitre. Modèle:Plume
• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.