Mot synchronisant

conjecture mathématique

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[1],[2]. 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ý.

Un automate fini sur deux lettres R et B. Le mot BRRBRRBRR est synchronisant et envoie tous les états sur l'état jaune ; le mot BBRBBRBBR aussi est synchronisant et envoie tous les états sur l'état vert.

Existence

modifier
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[3] 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é[2](en anglais synchronised automaton) ou synchronisable[4].

Conjecture de Černý

modifier

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[1],[5] :

Conjecture de Černý — Tout automate fini déterministe complet synchronisable à états possède un mot synchronisant de longueur au plus .

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é [2],[6]. Cette majoration est due à Jean-Éric Pin[7] et Peter Frankl[8]. Marek Szykuła annonce en 2017 une majoration légèrement meilleure[9] : elle est [10].

Paires synchronisables

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

É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.
La paire (1,4) du premier automate n'est pas 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

modifier

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 [3].

Automates apériodiques

modifier

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 :

Proposition (Trahtman (2008)[11]) — Un automate apériodique synchronisable à états possède un mot synchronisant de longueur au plus .

Cette borne a été améliorée par Volkov[12] 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

modifier

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[13] que tout graphe régulier fortement connexe et apériodique[14] peut être coloré de manière à avoir cette propriété ; leur conjecture a été démontrée en 2007 par Avraham Trahtman[15].

Bibliographie

modifier

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

Notes et références

modifier
  1. a b et c Avraham Trakhtman: Bibliographie (Cerny conjecture, road coloring, synchronizing word) sur la page de Trahtman.
  2. a b et c Béal et Perrin 2016.
  3. a et b Eppstein 1990
  4. Trahtman 2007.
  5. Černý 1964.
  6. Trahtman pensait avoir trouvé une meilleure majoration, mais sa preuve s'est avérée fausse et l’article a été retiré.
  7. Jean-Éric Pin, « On two Combinatorial Problems Arising from Automata Theory », Annals of Discrete Mathematics, vol. 17,‎ , p. 535–548 (ISSN 0304-0208, DOI 10.1016/S0304-0208(08)73432-7, lire en ligne).
  8. Peter Frankl, « An Extremal Problem for two Families of Sets », European Journal of Combinatorics, vol. 3, no 2,‎ , p. 125–127 (ISSN 0195-6698, DOI 10.1016/S0195-6698(82)80025-5).
  9. Marek Szykuła, « Improving the upper bound on the length of the shortest reset words », en cours,‎ (arXiv 1702.05455, lire en ligne, consulté le ).
  10. L'auteur indique que sa meilleure majoration est , mais qu'elle est moins lisible.
  11. Trahtman 2008.
  12. Volkov 2009.
  13. Adler et Weiss 1970.
  14. Un graphe orienté est apériodique s'il n'existe pas d'entier >1 qui divise les longueurs de tous ses circuits ou si, de manière équivalente, le pgcd des longueurs de ses chemin est 1.
  15. La preuve est publiée dans arXiv en 2007, l'article en revue en 2010 : Trahtman 2009.