Mot synchronisant

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

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 ${\displaystyle (n-1)^{2}}$ est un majorant de la longueur du plus court mot synchronisant dans un automate fini déterministe complet à ${\displaystyle n}$ états[1] - [5] :

La conjecture est encore ouverte ; dans son article de 1964, Ján Černý donne une classe d'automates, indexée par le nombre ${\displaystyle n}$ d'états, pour laquelle le plus court mot synchronisant est de longueur ${\displaystyle (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é ${\displaystyle (n^{3}-n)/6}$[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 ${\displaystyle 114n^{3}/685+O(n^{2})}$[10].

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

Étant donné un automate fini déterministe complet avec un ensemble ${\displaystyle Q}$ d'états, on note ${\displaystyle Q\cdot w=\{q\cdot w\mid q\in Q\}}$ et l’ensemble des états atteints à partir d'un état de ${\displaystyle Q}$ par le mot ${\displaystyle w}$. Le rang du mot ${\displaystyle w}$ est le nombre d'éléments de l'ensemble ${\displaystyle Q\cdot w}$. Un mot synchronisant est un mot de rang 1. Une paire d'états ${\displaystyle (p,q)}$ est synchronisable s'il existe un mot ${\displaystyle w}$ tel que ${\displaystyle 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 à ${\displaystyle 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.

Pour un automate à ${\displaystyle n}$ états sur un alphabet à ${\displaystyle k}$ lettres, David Eppstein donne un algorithme pour calculer une mot synchronisant de longueur au plus ${\displaystyle 11n^{3}/48+O(n^{2})}$ dont la complexité en temps est ${\displaystyle O(n^{3}+kn^{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 ${\displaystyle O(kn^{2})}$ fournit toujours un mot synchronisant de longueur au plus ${\displaystyle (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 ${\displaystyle (n-1)^{2}}$[3].

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 ${\displaystyle m}$ tel que, pour tout état ${\displaystyle q}$ et pour tout mot ${\displaystyle w}$, on a :

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

On peut noter qu'on a toujours ${\displaystyle q\cdot w^{m}=q\cdot w^{m+r}}$ pour un entier ${\displaystyle r>0}$ ; la particularité qui définit les automates apériodiques est que l'on peut choisir ${\displaystyle 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[12] dans le cas particulier des automates apériodiques fortement connexes. Il montre que la borne peut être remplacée par ${\displaystyle 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 ${\displaystyle n-1}$.

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

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.

• Roy L. Adler et Benjamen Weiss, Similarity of automorphisms of the torus, coll. « Memoires of the American Mathematical Society » (n^o 98), 1970, ii+48 (ISBN 978-1-4704-0048-4, MR 0257315).
• Marie-Pierre Béal et Dominique Perrin, chap. 7 « Synchronised automata », dans Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, Words and Symbolic Dynamics, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 135), 2016 (ISBN 978-0-521-51597-9, 9781139924733 et 9781107077027, DOI 10.1017/cbo9781139924733.008, présentation en ligne), p. 213-240.
• Natalie Behague et Robert Johnson, « Synchronizing times for k-sets in automata », The Electronic Journal of Combinatorics,‎ 26 août 2022, P3.41–P3.41 (DOI 10.37236/9819, lire en ligne)
• Ján Černý, « Poznámka k homogénnym experimentom s konečnými automatami », Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, vol. 14,‎ 1964, p. 208–216 (MR 168429, lire en ligne).
• David Eppstein, « Reset Sequences for Monotonic Automata », SIAM Journal on Computing, vol. 19, n^o 3,‎ 1990, p. 500–510 (DOI 10.1137/0219033, lire en ligne).
• Helmut Jürgensen, « Synchronization », Information and Computation, vol. 206, n^os 9–10,‎ 2008, p. 1033–1044 (DOI 10.1016/j.ic.2008.03.005).
• Cyril Nicaud, « The Černý Conjecture Holds with High Probability », Journal of Automata, Languages and Combinatorics, vol. 24, n^os 2–4,‎ 2019, p. 343-365 (DOI 10.25596/jalc-2019-343, présentation en ligne).
• Avraham N. Trahtman, « The Cerny Conjecture for Aperiodic Automata », Discrete Mathematics & Theoretical Computer Science, vol. 9, n^o 2,‎ 2007, p. 3-10 (HAL hal-00966534, lire en ligne).
• Avraham N. Trahtman, « Synchronizing road coloring », Fifth IFIP International Conference on Theoretical Computer Science, vol. 273,‎ 2008, p. 43–53.
• Avraham N. Trahtman, « The road coloring problem », Israel Journal of Mathematics, vol. 172, n^o 1,‎ 2009, p. 51–60 (DOI 10.1007/s11856-009-0062-5, arXiv 0709.0099).
• Mikhail V. Volkov, « Synchronizing Automata and the Černý Conjecture », dans Language and Automata Theory and Applications (LATA 2008), Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 5196), 2008 (lire en ligne), p. 11–27.
• Mikhail V. Volkov, « Synchronizing automata preserving a chain of partial orders », Theoretical Computer Science, vol. 410, n^o 37,‎ 2009, p. 3513–3519.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « synchronizing word » (voir la liste des auteurs).