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 finie fixe entre mots sur un alphabet donné, dont les éléments sont appelés les règles de réécriture, et notées . 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 , pour une règle de et des mots , et 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 , où est un alphabet supposé en général fini, et où est une relation binaire finie entre mots sur , donc une partie finie Un élément est une règle de réécriture et est habituellement écrite sous la forme . Si la relation est symétrique, c'est-à-dire si implique , le système est appelé un système de Thue.
Les règles de réécriture sont étendues aux mots de en permettant le remplacement de facteurs selon les règles de . Formellement la relation est étendue par :
si et seulement il existe tels que , , et .
On rencontre aussi la notation , ce qui permet d'omettre l'indice . La relation de réécriture, notée , est la clôture réflexive et transitive de la relation ; elle est définie par une suite d'étapes
Congruence de Thue
Dans un système de semi-Thue, la relation est compatible avec l'opération de multiplication (concaténation) du monoïde libre , en d'autres termes implique pour tous les mots . Comme est un préordre, le couple forme un préordre monoïdal.
De même, la clôture réflexive transitive et symétrique de , parfois dénotée par , 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 . 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 est une congruence, on peut définir le monoïde quotient du monoïde libre par la congruence de Thue, comme dans tout monoïde. Si un monoïde est isomorphe à , le système de semi-Thue est une présentation du monoïde . Par exemple, le système est une présentation du groupe libre à un générateur ; le système réduit à la seule règle est une présentation du demi-groupe bicyclique. De fait, on a : Tout monoïde admet une présentation de la forme 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 et deux mots , peut-on transformer en en appliquant des règles de ? Ce problème est indécidable. La première preuve est de Emil Post. Une autre, pratiquement en même temps, par A. Markov. Les preuves sont discutées dans le livre de Davis.
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 et Jean-Pierre Jouannaud. Rewrite Systems (1990) p. 6. 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, Introduction to Computer Theory, 2nd ed., Wiley-India, 2007, , p.572. 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 , où est appelé l'« ensemble des axiomes »Dan A. Simovici et Richard L. Tenney, Theory of formal languages with applications, World Scientific, 1999, , chapitre 4.
Notes
Bibliographie
Monographies
. . .
Manuels
.
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, .
— Réimpression avec corrections par Dover en 2004.
Articles historiques
— réimpression dans les Œuvres mathématiques, — réimpression dans les Œuvres mathématiques,
.
Voir aussi
L-Système Système de Post
Catégorie:Langage formel Catégorie:Grammaire Catégorie:Modèle de calcul