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
La congruence de Simon est une congruence sur des mots définie comme suit : deux mots sont équivalent à l'ordre s'ils ont même ensemble de sous-mots de longueur au plus . L'équivalence est notée .
Exemples
Par exemple, les mot et vérifient puisqu'ils ont les mêmes sous-mots de longueur au plus 2, à savoir .
Application
Un langage formel est testable par morceaux s'il existe un entier tel que est la réunion de classes de la congruence de Simon [1].
Test d'équivalence
Les problèmes algorithmiques sont présentés dans un article de synthè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 est lexicographiquement plus petit qu'un mot de même longueur s'il existe un préfixe de et un préfixe de avec que . Étant donné une congruence , la forme normale « shortlex » d'un mot est par définition le mot lexicographiquement le plus petit parmi les mots les plus courts de la classe de .
Ainsi, pour chaque classe d'équivalence de l’équivalence de Simon , 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 .
Test par automate
Il existe deux approches naturelles pour tester si . La première consiste en la construction d'un automate fini qui reconnaît les sous-mots de de longueur au plus et de même pour le mot . Alors 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 états. Par conséquent, le test résultant est presque linéaire en pour l'alphabet .
Calcul de formes normales
La deuxième approche pour tester si est le calcul de formes normales. Une forme normale est un représentant unique d'une classe . En particulier, on a si et seulement si si et 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 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 . Les formes normales pour et ont été examinées par Kátai-Urbán et al.[3]
Un algorithme pour le calcul des formes normales pour un entier arbitraire a été donné par Pach[4]. Son temps d'exécution est pour des entrées de longueur sur l'alphabet , c'est-à-dire qu'il est polynomial pour 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 de de longueur en temps même si fait partie de l'entrée. Ceci est surprenant puisque le nombre de sous-mots possibles croît exponentiellement avec . Quand , la classe d'équivalence de 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 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 -équivalents (avec 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
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
- Péter Pál Pach, « Normal forms under Simon’s congruence », Semigroup Forum, vol. 97, no 2, , 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, no 2, , 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, , 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, no 16, (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, , article no =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 », , p. 62:1--62:13 (DOI 10.4230/LIPIcs.MFCS.2018.62, lire en ligne, consulté le ).
- 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, , article no 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, 2e é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, (DOI 10.48550/arXiv.2308.08374)
Notes et références
- ↑ Imre Simon, « Piecewise testable events », Lect. Notes Comput. Sci., vol. 33 « Autom. Theor. form. Lang., 2nd GI Conf., Kaiserslautern », , p. 214-222.
- ↑ Fleischmann, Kim et Koß 2024.
- ↑ Kamilla Kátai-Urbán et al. 2012.
- ↑ Pach 2018.
- ↑ Fleischer et Kufleitner 2018.
- ↑ Laura Barker et al. 2020.
- ↑ Paweł Gawrychowski et al. 2020
- ↑ Kim, Ko et Han 2024.
Portail de l’algèbre
Portail de l'informatique théorique