Langage congruentiel

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un langage congruentiel est un langage formel qui est la réunion d'un nombre fini de classes d'une congruence sur l'alphabet donné. Un cas important est celui où la congruence est engendrée par un système de réécriture fini. Selon le type du système de réécriture, la complexité algorithmique du problème du mot peut être linéaire en temps, PSPACE-complet ou indécidable.

Les classes de langages congruentiels forment une autre hiérarchie de langages, incomparable à la hiérarchie de Chomsky.

Langages congruentiels[modifier | modifier le code]

Un système de réécriture sur un alphabet fini A est un ensemble fini de couples de mots sur A, appelées règles de réécriture , présentées sous la forme . 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 pour tout 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 . Ce langage est formé des mots d'une seule classe de la congruence engendrée par , à savoir la classe du mot vide.

Langages Church-Rosser congruentiels[modifier | modifier le code]

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 par la congruence engendrée par 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 sont Church-Rosser congruentiels (pour ce dernier, la réduction s'opère par la règle ); le langage 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].

Tout langage rationnel est Church-Rosser congruentiel[modifier | modifier le code]

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 , il existe une système de réécriture fini Church-Rosser tel que 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 , le membre droit ' est un sous-mot du membre gauche , c'est-à-dire obtenu en supprimant certaines lettres dans . Cette propriété est étendue pour la cas général comme suit : Une fonction de poids est une fonction qui à tout lettre 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 , on a .

Pour tout langage rationnel de , il existe un système de réécriture fini, confluent et réducteur en poids telle que le monoïde quotient est fini et reconnaît .

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

Systèmes presque confluents[modifier | modifier le code]

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 de mots équivalents, il existe deux mots et de même longueur avec et et tels que et 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 un langage rationnel de . Il existe un monoïde fini , un morphisme surjectif de sur , et une partie de tells que

.

Posons pour dans . La partition de en parties , pour dans , peut être réalisée par un système de réécriture presque confluent, comme suit : Pour tout de , soit un élément de longueur minimale de , et soit la longueur maximale des mots . Le système S des couples

est un système presque confluent, et ses classes de congruences coïncident avec les parties .

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 , la congruence engendrée par pour et les règles . Le monoïde quotient par la congruence définie par S est en fait l'anneau des entiers relatifs , et le langage , image inverse de , 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.

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

  1. a et b Robert McNaughton, Paliath Narendran et Friedrich Otto, « Church-Rosser Thue systems and formal languages », Journal of the ACM, vol. 35, no 2,‎ , p. 324-344 (DOI 10.1145/42282.42284).
  2. Colm Ó’Dúnlaing et Natalie Schluter, « A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems », Theoretical Computer Science, vol. 411, no 3,‎ , p. 677-690 (DOI 10.1016/j.tcs.2009.10.003).
  3. Volker Diekert, Manfred Kufleitner, Klaus Reinhardt et Tobias Walter, « Regular Languages Are Church-Rosser Congruential », 39th International Colloquium Automata, Languages, and Programming (ICALP), Springer Science + Business Media,‎ , p. 177-188 (DOI 10.1007/978-3-642-31585-5_19).
  4. a, b et c Volker Diekert, Manfred Kufleitner, Klaus Reinhardt et Tobias Walter, « Regular Languages Are Church-Rosser Congruential », Journal of the ACM, vol. 62, no 5,‎ , p. 1-20 (DOI 10.1145/2808227, arXiv 1202.1148/2808227).
  5. Klaus Reinhardt et Denis Thérien, « Some more regular languages that are Church Rosser congruential », 13. Theorietag, Automaten und Formale Sprachen, Herrsching (Allemagne),‎ , p. 97–103 (lire en ligne).
  6. Volker Diekert, Manfred Kufleitner et Pascal Weil, « Star-free languages are Church-Rosser congruential », Theoretical Computer Science, vol. 454,‎ , p. 129-135 (DOI 10.1016/j.tcs.2012.01.028).
  7. Ronald V. Book et Friedrich Otto, String-Rewriting Systems, Springer Science & Business Media, coll. « Texts and Monographs in Computer Sciencelieu = », , viii+189 p. (ISBN 9781461397717, DOI 10.1007/978-1-4613-9771-7).
  8. a et b (en) Colm Ó Dúnlaing, « An almost-confluent congruential language which is not Church–Rosser congruential », Theoretical Computer Science, vol. 589,‎ , p. 141–146 (DOI 10.1016/j.tcs.2015.04.018). Une version préliminaire intitulée « an ACCL not a CRCL », est sur le site arXiv.

Voir aussi[modifier | modifier le code]