Système de Thue

En informatique théorique et en logique mathématique, un système de semi-Thue ou sa version symétrique, un système de Thue, est un système de réécriture de chaînes de caractères ou mots, appelé ainsi d'après son inventeur, le mathématicien norvégien Axel Thue. Contrairement aux grammaires formelles, un tel système ne distingue pas entre symboles terminaux et non terminaux, et ne possède pas d'axiome.

Un système de semi-Thue est donné par une relation binaire $R$ finie fixe entre mots sur un alphabet donné, dont les éléments sont appelés les règles de réécriture, et notées $s\to t$. La relation est étendue en une relation de réécriture entre tous les mots dans lesquels les parties gauche et droite d'une règle apparaissent en facteur, en d'autres termes on a la relation $usv\to utv$, pour une règle $s\to t$ de $R$ et des mots $u$, et $v$ quelconques.

Les systèmes de semi-Thue sont Turing-complets. Ils sont voisins des systèmes de Post. Axel Thue a étudié les systèmes de réécriture dans deux articles, l'un sur la réécriture de termes, l'autre sur la réécriture des mots ; c'est du deuxième que dérivent les systèmes de semi-Thue.

Le problème de décider de l'existence d'une relation entre deux mots est indécidable.

Définition

Un système de semi-Thue est un couple $(\mathrm{\Sigma },R)$, où $\mathrm{\Sigma }$ est un alphabet supposé en général fini, et où $R$ est une relation binaire finie entre mots sur $\mathrm{\Sigma }$, donc une partie finie $R\subseteq {\mathrm{\Sigma }}^{*}\times {\mathrm{\Sigma }}^{*}.$ Un élément $(u,v)\in R$ est une règle de réécriture et est habituellement écrite sous la forme $u\to v$. Si la relation $R$ est symétrique, c'est-à-dire si $(u,v)\in R$ implique $(v,u)\in R$, le système est appelé un système de Thue.

Les règles de réécriture sont étendues aux mots de ${\mathrm{\Sigma }}^{*}$ en permettant le remplacement de facteurs selon les règles de $R$. Formellement la relation est étendue par :

$s{\to }_{R}t$ si et seulement il existe $x,y,u,v\in {\mathrm{\Sigma }}^{*}$ tels que $s=xuy$, $t=xvy$, et $u\to v\in R$.

On rencontre aussi la notation $s\Rightarrow t$, ce qui permet d'omettre l'indice $R$. La relation de réécriture, notée $\underset{R}{\overset{*}{\to }}$, est la clôture réflexive et transitive de la relation ${\to }_R$; elle est définie par une suite d'étapes

$s_0{\to }_R{s}_1{\to }_R{s}_2{\to }_R\cdots$

Congruence de Thue

Dans un système de semi-Thue, la relation $\underset{R}{\overset{*}{\to }}$ est compatible avec l'opération de multiplication (concaténation) du monoïde libre ${\mathrm{\Sigma }}^{*}$, en d'autres termes $x\underset{R}{\overset{*}{\to }}y$ implique $uxv\underset{R}{\overset{*}{\to }}uyv$ pour tous les mots $u,v\in {\mathrm{\Sigma }}^{*}$. Comme $\underset{R}{\overset{*}{\to }}$ est un préordre, le couple $({\mathrm{\Sigma }}^{*},\cdot ,\underset{R}{\overset{*}{\to }})$ forme un préordre monoïdal.

De même, la clôture réflexive transitive et symétrique de ${\to }_R$, parfois dénotée par $\stackrel{*}{⟷R}$, est une congruence, c'est-à-dire une relation d'équivalence compatible avec la concaténation. Cette congruence est appelée congruence de Thue engendrée par $R$. Si le système de semi-Thue est symétrique, donc un système de Thue, la congruence coïncide avec la relation de réécriture.

Comme $\stackrel{*}{⟷R}$ est une congruence, on peut définir le monoïde quotient $M_R={\mathrm{\Sigma }}^{*}/\stackrel{*}{⟷R}$ du monoïde libre ${\mathrm{\Sigma }}^{*}$ par la congruence de Thue, comme dans tout monoïde. Si un monoïde $ℳ$ est isomorphe à $M_R$, le système de semi-Thue $(\mathrm{\Sigma },R)$ est une présentation du monoïde $ℳ$. Par exemple, le système $R=\{ab\to \epsilon ,ba\to \epsilon \}$ est une présentation du groupe libre à un générateur ; le système réduit à la seule règle $ab\to \epsilon$ est une présentation du demi-groupe bicyclique. De fait, on aModèle:Sfn : Tout monoïde admet une présentation de la forme $(\mathrm{\Sigma },R)$ pour un système de semi-Thue, éventuellement sur un alphabet infini.

Le problème du mot

Le problème du mot pour un système de semi-Thue se formule comme suit : Étant donné un système de semi-Thue $(\mathrm{\Sigma },R)$ et deux mots $u,v\in {\mathrm{\Sigma }}^{*}$, peut-on transformer $u$ en $v$ en appliquant des règles de $R$ ? Ce problème est indécidable. La première preuve est de Emil PostModèle:Sfn. Une autre, pratiquement en même temps, par A. MarkovModèle:Sfn. Les preuves sont discutées dans le livre de DavisModèle:Sfn.

Connexions avec d'autres concepts

Un système de semi-Thue peut être vu comme un système de réécriture de termes dont les mots sont des termes d'arité 1. Un système de semi-Thue est aussi un cas particulier d'un système de Post, et réciproquement tout système de Post peut être transformé en un système de semi-Thue. Les deux formalismes sont Turing-complets, et sont donc équivalents aux grammaires de type 0 de la hiérarchie de Chomsky qui parfois sont appelées grammaires de semi-Thue. Une grammaire formelle diffère d'un système de semi-Thue par la séparation de l’alphabet en symboles terminaux et non terminaux et la présence d'un axiome. On rencontre aussi la définition d'un système de semi-Thue comme triple $(\mathrm{\Sigma },A,R)$, où $A\subseteq {\mathrm{\Sigma }}^{*}$ est appelé l'« ensemble des axiomes ».

Bibliographie

Monographies

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

Manuels

• Modèle:Ouvrage
• Modèle:Ouvrage.

Chapitres de manuels

• Samson Abramsky, Dov M. Gabbay, Thomas S. E. Maibaum (ed.), Handbook of Logic in Computer Science: Semantic modelling, Oxford University Press, 1995, Modèle:Isbn.

• Modèle:Chapitre
• Modèle:Chapitre
• Modèle:Ouvrage — Réimpression avec corrections par Dover en 2004.

Articles historiques

• Modèle:Article — réimpression dans les Œuvres mathématiques, Modèle:P.
• Modèle:Article — réimpression dans les Œuvres mathématiques, Modèle:P.
• Modèle:OuvrageModèle:Commentaire biblio
• Modèle:Article.
• Modèle:Article

Voir aussi

• L-Système
• Système de Post

Modèle:Palette Langages formels grammaires et automates Modèle:Portail