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

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 modifier

Par exemple, les mot   et   vérifient   puisqu'ils ont les mêmes sous-mots de longueur au plus 2, à savoir  .

Application modifier

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 modifier

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   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  . Etant 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 modifier

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 modifier

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 modifier

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

  • 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 modifier

  1. Imre Simon, « Piecewise testable events », Lect. Notes Comput. Sci., vol. 33 « Autom. Theor. form. Lang., 2nd GI Conf., Kaiserslautern »,‎ , p. 214-222.
  2. Fleischmann, Kim et Koß 2024.
  3. Kamilla Kátai-Urbán et al. 2012.
  4. Pach 2018.
  5. Fleischer et Kufleitner 2018.
  6. Laura Barker et al. 2020.
  7. Paweł Gawrychowski et al. 2020
  8. Kim, Ko et Han 2024.