Langage congruentiel

Un système de réécriture sur un alphabet fini A est un ensemble fini de couples de mots ${\displaystyle (r,r')}$ sur A, appelées règles de réécriture, présentées sous la forme ${\displaystyle r\to r'}$. Un tel système est aussi parfois appelé système de semi-Thue ou système semi-thuéien. Le système est décroissant en longueur si ${\displaystyle |r|>|r'|}$ pour toute règle. Il est Church-Rosser s'il est confluent ou si, de manière équivalente, il vérifie la propriété de Church-Rosser.

Un langage formel L est congruentiel s'il existe un système de réécriture fini S tel que L est une union finie de classes de congruences modulo S. Selon les propriétés du système de réécriture, la classe des langages congruentiels est plus ou moins restreinte.

Un langage L est Church-Rosser congruentiel si L est une union finie de classes de congruences modulo un système de réécriture Church-Rosser décroissant.

L'exemple paradigmatique est le langage de Dyck sur une paire de lettres ${\displaystyle a,{\bar {a}}}$. Ce langage est formé des mots d'une seule classe de la congruence engendrée par ${\displaystyle a{\bar {a}}\to \varepsilon }$, à savoir la classe du mot vide.

La classe des langages Church-Rosser congruentiels a été introduite en 1988 par McNaughton, Narendran, et Otto[1].

Une des motivations principales pour l'étude de cette classe de langages est que le problème de l'appartenance peut être résolu en temps linéaire : dans un système Church-Rosser, toute classe possède un élément irréductible unique; lorsque le système est de plus décroissant, pour chaque mot, cette forme normale d'un mot peut être calculée en réduisant le mot selon les règles du système il suffit alors de tester si le mot réduit figure dans la liste finie des représentants des classes dont le langage est la réunion.

Pour opérer ce test, il n'est donc pas nécessaire que le monoïde quotient ${\displaystyle A^{*}/S}$ par la congruence engendrée par ${\displaystyle S}$ soit fini, seul le nombre de classes dont le langage est la réunion doit être fini.

En plus de l'exemple du langage de Dyck, le langage de Lukasiewicz, le langage ${\displaystyle \{a^{n}b^{n}\mid n\geq 0\}}$ sont Church-Rosser congruentiels (pour ce dernier, la réduction s'opère par la règle ${\displaystyle a^{2}b^{2}\to ab}$); le langage ${\displaystyle \{a^{n}b^{m}\mid n\geq m\geq 0\}}$ ne l'est pas. Le langage des palindromes n’est pas Church-Rosser[2]. Un langage algébrique déterministe n'est pas toujours Church-Rosser congruentiel. McNaughton, Narendran, et Otto définissent une famille plus générale de langages qu'ils appellent « CRDL », pour langages Church-Rosser décidables, et montrent que tout langage algébrique déterministe est Church-Rosser décidable[1].

Pendant longtemps, la propriété que tout langage rationnel est Church-Rosser congruentiel est restée à l'état de conjecture. En 2012, une démonstration est annoncée lors de la conférence ICALP[3], puis elle est publiée en 2015[4].

Auparavant, en 2003, Klaus Reinhardt et Denis Thérien annoncent[5] que tout langage rationnel dont le monoïde syntaxique est un groupe est Church-Rosser congruentiel, mais cet article n'est pas publié en revue, et la correction est mise en doute[4].

Un résultat intermédiaire de Volker Diekert, Manfred Kufleitner et Pascal Weil paru en 2012[6] montre que tout langage sans étoile est Church-Rosser congruentiel. Pour ce faire, les auteurs prouvent que, pour tout langage sans étoile ${\displaystyle L}$, il existe un système de réécriture fini Church-Rosser tel que ${\displaystyle L}$ est union d'un nombre fini de classes d'équivalence, et qui possède la propriété remarquable supplémentaire que pour toute règle ${\displaystyle r\to r'}$, le membre droit ${\displaystyle r}$' est un sous-mot du membre gauche ${\displaystyle r}$, c'est-à-dire obtenu en supprimant certaines lettres dans ${\displaystyle r}$. Cette propriété est étendue pour le cas général comme suit : Une fonction de poids est une fonction ${\displaystyle \|\cdot \|\to \mathbb {N} }$ qui à tout lettre ${\displaystyle a\in A}$ associe un entier positif, et qui est étendue additivement aux mots. Un système de réécriture est réducteur en poids si, pour toute règle ${\displaystyle r\to r'}$, on a ${\displaystyle \|r\|>\|r'\|}$.

Pour tout langage rationnel ${\displaystyle L}$ de ${\displaystyle A^{*}}$, il existe un système de réécriture fini, confluent et réducteur en poids ${\displaystyle S}$ telle que le monoïde quotient ${\displaystyle A^{*}/S}$ est fini et reconnaît ${\displaystyle L}$.

Cette propriété donne une nouvelle caractérisation des langages rationnels[4].

Un système de réécriture moins contraignant est connu sous le terme de système presque confluent[7]. Un système est presque confluent si, pour toute paire ${\displaystyle x,y}$ de mots équivalents, il existe deux mots ${\displaystyle z_{1}}$ et ${\displaystyle z_{2}}$ de même longueur avec ${\displaystyle x{\overset {*}{\to }}z_{1}}$ et ${\displaystyle y{\overset {*}{\to }}z_{2}}$ et tels que ${\displaystyle z_{1}}$ et ${\displaystyle z_{2}}$ peuvent être réécrits l’un dans l’autre par des règles qui préservent la longueur.

Un langage congruentiel presque confluent est un langage qui est réunion fini de classes d’une congruence presque confluente. Alors que le problème de l'appartenance est de complexité linéaire pour un système Church-Rosser décroissant, il est PSPACE-complet pour les systèmes presque confluents.

Il est facile de voir que tout langage rationnel est presque confluent[8]. Soit en effet ${\displaystyle L}$ un langage rationnel de ${\displaystyle A^{*}}$. Il existe un monoïde fini ${\displaystyle M}$, un morphisme surjectif ${\displaystyle h}$ de ${\displaystyle A^{*}}$ sur ${\displaystyle M}$, et une partie ${\displaystyle P}$ de ${\displaystyle M}$ tells que

${\displaystyle L=\bigcup _{p\in P}h^{-1}(p)}$.

Posons ${\displaystyle K_{m}=h^{-1}(m)}$ pour ${\displaystyle m}$ dans ${\displaystyle M}$. La partition de ${\displaystyle A^{*}}$ en parties ${\displaystyle K_{m}}$, pour ${\displaystyle m}$ dans ${\displaystyle M}$, peut être réalisée par un système de réécriture presque confluent, comme suit : Pour tout ${\displaystyle m}$ de ${\displaystyle M}$, soit ${\displaystyle y_{m}}$ un élément de longueur minimale de ${\displaystyle K_{m}}$, et soit ${\displaystyle N}$ la longueur maximale des mots ${\displaystyle y_{m}}$. Le système S des couples

${\displaystyle S=\{(x,y_{m})\mid x\in K_{m},\ |x|\leq 1+N\}}$

est un système presque confluent, et ses classes de congruences coïncident avec les parties ${\displaystyle K_{m}}$.

Cette propriété des langages rationnels est moins précise que celle par Church-Rosser, et en effet il existe des langages congruentiels presque confluents qui ne sont pas Church-Rosser congruentiels. Un tel exemple est donné par Colm Ó Dúnlaing[8]. On considère, sur l'alphabet ${\displaystyle A=\{a,b,{\bar {a}},{\bar {b}}\}}$, la congruence engendrée par ${\displaystyle x{\bar {y}}\to \varepsilon ,{\bar {x}}y\to \varepsilon }$ pour ${\displaystyle x,y\in \{a,b\}}$ et les règles ${\displaystyle a\to b,b\to a,{\bar {a}}\to {\bar {b}},{\bar {b}}\to {\bar {a}}}$. Le monoïde quotient par la congruence définie par S est en fait l'anneau des entiers relatifs ${\displaystyle \mathbb {Z} }$, et le langage ${\displaystyle L}$, image inverse de ${\displaystyle 0}$, est composé des mots qui ont autant de lettres barrées que non barrées. Ce langage est presque confluent, et n'est pas Church-Rosser congruentiel.