Mot synchronisant

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 état<ref name=trakht-syn>
Avraham Trakhtman: [http://www.cs.biu.ac.il/~trakht/syn.html Bibliographie (Cerny conjecture, road coloring, synchronizing word)] sur la page de Trahtman.</ref>. 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 

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  est un majorant de la longueur du plus court mot synchronisant dans un automate fini déterministe complet à  états :

La conjecture est encore ouverte ; dans son article de 1964, Ján Černý donne une classe d'automates, indexée par le nombre  d'états, pour laquelle le plus court mot synchronisant est de longueur  ; 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é . Cette majoration est due à Jean-Éric Pin et Peter Frankl. Marek Szykuła annonce en 2017 une majoration légèrement meilleure : elle est .

 Paires synchronisables 

Étant donné un automate fini déterministe complet avec un ensemble  d'états, on note  et l’ensemble des états atteints à partir d'un état de  par le mot . Le rang du mot  est le nombre d'éléments de l'ensemble . Un mot synchronisant est un mot de rang 1. Une paire d'états  est synchronisable s'il existe un mot  tel que . L'énoncé de Černý annoncé plus haut est le suivant :
 Un automate est synchronisable si et seulement si toute paire d'états est synchronisable.Pour tester si un automate fini déterministe complet à  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 à  états sur un alphabet à  lettres, David Eppstein donne un algorithme pour calculer une mot synchronisant de longueur au plus  dont la complexité en temps est . 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  fournit toujours un mot synchronisant de longueur au plus  (la borne de Černý) et donne des automates de cette forme particulière pour lesquels le plus court mot synchronisant a exactement la longueur .

 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  tel que, pour tout état  et pour tout mot , on a :
.
On peut noter qu'on a toujours  pour un entier  ; la particularité qui définit les automates apériodiques est que l'on peut choisir . 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  ; en fait, on ne connaît pas d'automates fortement connexe apériodique qui n'a pas de mot synchronisant de longueur au plus .

 Coloriage des routes 

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.

 .

 . 
 

 .

 .

 .

 .

 .
 .
 .

 .
 .

Notes et références 

Combinatoire
Théorie des automates
Théorie des graphes
Cerny