Congruence de Simon

En informatique théorique, en combinatoire des mots et en théorie des langages formels, la congruence de Simon est une congruence sur les mots étudiée au départ notamment par Imre Simon dans le cadre de ses études sur les automates finis, congruence qui porte son nom. Elle a fait depuis l'objet de nombreux travaux combinatoires, algébriques et algorithmiques.

Définition[modifier | modifier le code]

La congruence de Simon est une congruence sur des mots définie comme suit : deux mots sont équivalent à l'ordre ${\displaystyle k}$ s'ils ont même ensemble de sous-mots de longueur au plus ${\displaystyle k}$. L'équivalence est notée ${\displaystyle \sim _{k}}$.

Exemples[modifier | modifier le code]

Par exemple, les mot ${\displaystyle x=abaab}$ et ${\displaystyle y=baba}$ vérifient ${\displaystyle x\sim _{2}y}$ puisqu'ils ont les mêmes sous-mots de longueur au plus 2, à savoir ${\displaystyle \{\varepsilon ,a,b,aa,ab,ba,bb\}}$.

Application[modifier | modifier le code]

Un langage formel ${\displaystyle L}$ est testable par morceaux s'il existe un entier ${\displaystyle k}$ tel que ${\displaystyle L}$ est la réunion de classes de la congruence de Simon ${\displaystyle \sim _{k}}$^[1].

Test d'équivalence[modifier | modifier le code]

Les problèmes algorithmiques sont présentés dans un article de sythèse par Pamela Fleischmann, Sungmin Kim, Tore Koß et. al.^[2].

On suppose que les lettres de l'alphabet sont totalement ordonnées. Un mot ${\displaystyle u}$ est lexicographiquement plus petit qu'un mot ${\displaystyle v}$ de même longueur s'il existe un préfixe ${\displaystyle pa}$ de ${\displaystyle u}$ et un préfixe ${\displaystyle pb}$ de ${\displaystyle v}$ avec que ${\displaystyle a<b}$. Etant donné une congruence ${\displaystyle \sim }$, la forme normale « shortlex » d'un mot ${\displaystyle u}$ est par définition le mot ${\displaystyle v}$ lexicographiquement le plus petit parmi les mots les plus courts de la classe ${\displaystyle \sim }$ de ${\displaystyle u}$.

Ainsi, pour chaque classe d'équivalence de l’équivalence de Simon ${\displaystyle \sim _{k}}$, on peut définir un représentant canonique en forme normale « shortlex » : c'est le mot minimal pour l'ordre lexicographique parmi les mots les plus courts de ${\displaystyle \sim _{k}}$.

Test par automate[modifier | modifier le code]

Il existe deux approches naturelles pour tester si ${\displaystyle u\sim _{k}v}$. La première consiste en la construction d'un automate fini qui reconnaît les sous-mots de ${\displaystyle u}$ de longueur au plus ${\displaystyle k}$ et de même pour le mot ${\displaystyle v}$. Alors${\displaystyle u\sim _{k}v}$ si et seulement si ces deux automates acceptent le même langage. Ceci peut être testé avec l'algorithme de Hopcroft de minimisation d'un automate fini en un temps presque linéaire dans la taille des automates. Il est possible de construire les automates de telle sorte qu'ils aient au plus ${\displaystyle k|u|+2}$ états. Par conséquent, le test résultant est presque linéaire en ${\displaystyle |A|k|uv|}$ pour l'alphabet ${\displaystyle A}$.

Calcul de formes normales[modifier | modifier le code]

La deuxième approche pour tester si ${\displaystyle u\sim _{k}v}$ est le calcul de formes normales. Une forme normale est un représentant unique d'une classe ${\displaystyle \sim _{k}}$. En particulier, on a ${\displaystyle u\sim _{k}v}$ si et seulement si si ${\displaystyle u}$ et ${\displaystyle v}$ ont la même forme normale. En calculant les formes normales de ces deux mots et en vérifiant ensuite si elles sont identiques, la complexité du test de ${\displaystyle u\sim _{k}v}$ se réduit à celle du calcul des formes normales. Le calcul des formes normales est également intéressant en soi puisqu'il peut donner des informations sur les propriétés combinatoires de ${\displaystyle \sim _{k}}$. Les formes normales pour ${\displaystyle k=2}$ et ${\displaystyle k=3}$ ont été examinées par Kátai-Urbán et al.^[3]

Un algorithme pour le calcul des formes normales pour un entier ${\displaystyle k}$ arbitraire a été donné par Pach^[4]. Son temps d'exécution est ${\displaystyle O(|A|k(n+|A|))}$ pour des entrées de longueur ${\displaystyle n}$ sur l'alphabet ${\displaystyle A}$, c'est-à-dire qu'il est polynomial pour ${\displaystyle k}$ fixé et exponentiel sinon.

Lukas Fleischer et Manfred Kufleitner^[5] ont présenté un algorithme pour calculer le représentant canonique de la classe d'un mot ${\displaystyle w}$ de ${\displaystyle A^{*}}$ de longueur ${\displaystyle n}$ en temps ${\displaystyle O(|A|n)}$ même si ${\displaystyle k\leq n}$ fait partie de l'entrée. Ceci est surprenant puisque le nombre de sous-mots possibles croît exponentiellement avec ${\displaystyle k}$. Quand ${\displaystyle k>n}$, la classe d'équivalence de ${\displaystyle w}$ est un singleton. Pour un alphabet fixe, le temps d'exécution de leur algorithme est linéaire en la taille du mot d'entrée. De plus, pour un alphabet fixe, le calcul des formes normales « shortlex » pour ${\displaystyle \sim _{k}}$ est possible dans un espace logarithmique déterministe. Une des conséquences de leur algorithme est que l'on peut vérifier avec la même complexité si deux mots sont ${\displaystyle \sim _{k}}$-équivalents (avec ${\displaystyle k}$ faisant partie de l'entrée).

Barker et al.^[6] ont décrit un algorithme de normalisation qui améliore l'algorithme de Fleischer et Kufleitner et qui fournit un algorithme en temps linéaire. Ultérieurement, Gawrychowski et al.^[7] ont proposé une structure de données qui permet de trouver la valeur maximale en temps linéaire.

Variantes algorithmiques[modifier | modifier le code]

Des variantes sont présentés par Kim, Ko et Han^[8]. Elles concernent le calcul des sousmots d'un texte qui sont congrus à un motif donné.

Bibliographie[modifier | modifier le code]

• Péter Pál Pach, « Normal forms under Simon’s congruence », Semigroup Forum, vol. 97, n^o 2,‎ 1^er octobre 2018, p. 251–267 (DOI 10.1007/s00233-017-9910-5)

• Kamilla Kátai-Urbán, Péter Pál Pach, Gabriella Pluhár et András Pongrácz, « On the word problem for syntactic monoids of piecewise testable languages », Semigroup Forum, vol. 84, n^o 2,‎ 1^er avril 2012, p. 323–332 (DOI 10.1007/s00233-011-9357-z, zbMATH Zbl 1261.20075)

• Laura Barker, Pamela Fleischmann, Katharina Harwardt et Florin Manea, « Scattered Factor-Universality of Words », Developments in Language Theory, Springer International Publishing,‎ 2020, p. 14–28 (ISBN 978-3-030-48516-0, DOI 10.1007/978-3-030-48516-0_2)

• Paweł Gawrychowski, Martin Lange, Narad Rampersad et Jeffrey Shallit, « Existential Length Universality », 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, vol. LIPIcs.STACS.2020, n^o 16,‎ 2020 (DOI 10.4230/LIPIcs.STACS.2020.16, lire en ligne)

• Sungmin Kim, Sang-Ki Ko et Yo-Sub Han, « Simon's congruence pattern matching », Theoretical Computer Science, vol. 994,‎ mai 2024, article n^o =114478 (DOI 10.1016/j.tcs.2024.114478)

• Lukas Fleischer et Manfred Kufleitner, « Testing Simon's congruence », Leibniz International Proceedings in Informatics (LIPIcs), vol. 117 « MFCS 2018 »,‎ 2018, p. 62:1--62:13 (DOI 10.4230/LIPIcs.MFCS.2018.62, lire en ligne, consulté le 2 octobre 2023).
• Pamela Fleischmann, Lukas Haschke, Jonas Höfer et Annika Huch, « Nearly k-universal words – Investigating a part of Simon's congruence », Theoretical Computer Science, vol. 974,‎ 29 septembre 2023, article n^o 114113 (DOI 10.1016/j.tcs.2023.114113)
• Jacques Sakarovitch et Imre Simon, « Subwords », dans M. Lothaire, Combinatorics on words, Cambridge University Press, 1983, 1997, 2^e éd. (ISBN 978-0-521-59924-5), p. 105-144.
• Pamela Fleischmann, Sungmin Kim, Tore Koß, Florin Manea, Dirk Nowotka, Stefan Siemer et Max Wiedenhöft, « Matching Patterns with Variables Under Simon's Congruence », Arxiv,‎ 16 août 2023 (DOI 10.48550/arXiv.2308.08374)

Notes et références[modifier | modifier le code]

• Portail de l’algèbre
• Portail de l'informatique théorique