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^[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ý.

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^[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ý

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$ états^[1]^,^[5] :

Conjecture de Černý — Tout automate fini déterministe complet synchronisable à $n$ états possède un mot synchronisant de longueur au plus $(n-1)^{2}$ .

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$ ^[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 $114n^{3}/685+O(n^{2})$ ^[10].

Paires synchronisables

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

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}+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 $O(kn^{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}$ ^[3].

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 :

Proposition (Trahtman (2008)^[11]) — Un automate apériodique synchronisable à $n$ états possède un mot synchronisant de longueur au plus $(n-1)^{2}/2$ .

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 $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

Article détaillé : 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^[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

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.

Notes et références

(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).

↑ ^{a b et c} Avraham Trakhtman: Bibliographie (Cerny conjecture, road coloring, synchronizing word) sur la page de Trahtman.
↑ ^{a b et c} Béal et Perrin 2016.
↑ ^{a et b} Eppstein 1990
↑ Trahtman 2007.
↑ Černý 1964.
↑ Trahtman pensait avoir trouvé une meilleure majoration, mais sa preuve s'est avérée fausse et l’article a été retiré.
↑ Jean-Éric Pin, « On two Combinatorial Problems Arising from Automata Theory », Annals of Discrete Mathematics, vol. 17,‎ 1983, p. 535–548 (ISSN 0304-0208, DOI 10.1016/S0304-0208(08)73432-7, lire en ligne).
↑ Peter Frankl, « An Extremal Problem for two Families of Sets », European Journal of Combinatorics, vol. 3, n^o 2,‎ 1982, p. 125–127 (ISSN 0195-6698, DOI 10.1016/S0195-6698(82)80025-5).
↑ Marek Szykuła, « Improving the upper bound on the length of the shortest reset words », en cours,‎ 27 novembre 2017 (arXiv 1702.05455, lire en ligne, consulté le 3 février 2018).
↑ L'auteur indique que sa meilleure majoration est $(85059n^{3}+90024n^{2}+196504n-10648)/511104$ , mais qu'elle est moins lisible.
↑ Trahtman 2008.
↑ Volkov 2009.
↑ Adler et Weiss 1970.
↑ 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.
↑ La preuve est publiée dans arXiv en 2007, l'article en revue en 2010 : Trahtman 2009.

Portail de l'informatique théorique

[trakht-syn-1] {a b et c} Avraham Trakhtman: Bibliographie (Cerny conjecture, road coloring, synchronizing word) sur la page de Trahtman.

[bp-2] {a b et c} Béal et Perrin 2016.

[eppstein-3] {a et b} Eppstein 1990

[4] Trahtman 2007.

[cerny-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é.

[Pin1983-7] Jean-Éric Pin, « On two Combinatorial Problems Arising from Automata Theory », Annals of Discrete Mathematics, vol. 17,‎ 1983, p. 535–548 (ISSN 0304-0208, DOI 10.1016/S0304-0208(08)73432-7, lire en ligne).

[Frankl1982-8] Peter Frankl, « An Extremal Problem for two Families of Sets », European Journal of Combinatorics, vol. 3, n^o 2,‎ 1982, 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,‎ 27 novembre 2017 (arXiv 1702.05455, lire en ligne, consulté le 3 février 2018).

[10] L'auteur indique que sa meilleure majoration est $(85059n^{3}+90024n^{2}+196504n-10648)/511104$ , 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]