# 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 $k$ s'ils ont même ensemble de sous-mots de longueur au plus $k$. L'équivalence est notée $\sim _{k}$.

## Exemples

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

## Application

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

## 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..
On suppose que les lettres de l'alphabet sont totalement ordonnées. Un mot $u$ est lexicographiquement plus petit qu'un mot $v$ de même longueur s'il existe un préfixe $pa$ de $u$ et un préfixe $pb$ de $v$ avec que $a<b$. Étant donné une congruence $\sim$, la forme normale « shortlex » d'un mot $u$ est par définition le mot $v$ lexicographiquement le plus petit parmi les mots les plus courts de la classe $\sim$ de $u$.
Ainsi, pour chaque classe d'équivalence de l’équivalence de Simon $\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 $\sim _{k}$.

### Test par automate

Il existe deux approches naturelles pour tester si $u\sim _{k}v$. La première consiste en la construction d'un automate fini qui reconnaît les sous-mots de $u$ de longueur au plus $k$ et de même pour le mot $v$. Alors$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 $k|u|+2$ états. Par conséquent, le test résultant est presque linéaire en $|A|k|uv|$ pour l'alphabet $A$.

### Calcul de formes normales

La deuxième approche pour tester si $u\sim _{k}v$ est le calcul de formes normales. Une forme normale est un représentant unique d'une classe $\sim _{k}$. En particulier, on a $u\sim _{k}v$ si et seulement si si $u$ et $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 $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 $\sim _{k}$. Les formes normales pour $k=2$ et $k=3$ ont été examinées par Kátai-Urbán et al.
Un algorithme pour le calcul des formes normales pour un entier $k$ arbitraire a été donné par Pach. Son temps d'exécution est $O(|A|k(n+|A|))$ pour des entrées de longueur $n$ sur l'alphabet $A$, c'est-à-dire qu'il est polynomial pour $k$ fixé et exponentiel sinon.
Lukas Fleischer et Manfred Kufleitner ont présenté un algorithme pour calculer le représentant canonique de la classe d'un mot $w$ de $A^{*}$ de longueur $n$ en temps $O(|A|n)$ même si $k\leq n$ fait partie de l'entrée. Ceci est surprenant puisque le nombre de sous-mots possibles croît exponentiellement avec $k$. Quand $k>n$, la classe d'équivalence de $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 $\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 $\sim _{k}$-équivalents (avec $k$ faisant partie de l'entrée).
Barker et al. 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. 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. Elles concernent le calcul des sousmots d'un texte qui sont congrus à un motif donné.