Régularité et algébricité des systèmes de récriture

On peut trouver dans la littérature de nombreuses classes de systèmes de récriture préservant la régularité ou l’algébricité. Par exemple, la dérivation préfixe de tout système fini de récriture préserve la régularité [Bu 64, Ca 90]. De plus, les systèmes algébriques (tout membre gauche est de longueur au plus 1) préservent l’algébricité et leurs dérivations inverses préservent la régularité (voir par exemple [BO 93]). Dans [HW 04], Hofbauer et Waldmann ont montré que la dérivation de tout système effaçant fini préserve la régularité sachant que Hibbard [Hi 74] avait établi que la dérivation inverse préserve l’algébricité. Au lieu d’utiliser des règles de découpage et d’élimination, ils ont fourni une décomposition astucieuse de la relation de dérivation en une substitution finie suivie par la dérivation d’un système algébrique inverse et une restriction à l’alphabet original. De là, ils ont pu déduire de nombreux résultats déjà connus de préservation de la régularité et/ou de l’algébricité. La contribution principale de ce chapitre est de simplifier l’idée de la décomposition de dérivation de Hofbauer et Waldmann dans [HW 04] et de l’étendre à des familles plus générales de systèmes de récriture de mots.

En vertu de certains critères syntaxiques, cette étape de simulation peut être utilisée pour éliminer entièrement les règles de récriture du système initial. Plus précisément, nous sommes capable de décomposer la dérivation d’un système R en une substitution (régulière) dont le rôle est d’insérer des facteurs (tels que décrits ci dessus) correspondants à un sous-ensemble R′ de R, suivie par la dérivation d’un système S ∪ D, où S est tout simplement R − R′ et D désigne le système de Dyck. On dit que R est décomposable en S. En conséquence, la dérivation de R (resp. R−1 ) préserve la régularité (resp. l’algébricité) si c’est le cas pour la dérivation de S ∪ D (resp. son inverse). Cela reste vrai même pour les systèmes infinis lorsque le système R′ est reconnaissable.

Ce résultat peut être utilisé pour caractériser quelques familles de systèmes dont la dérivation préserve la régularité ou l’algébricité. Premièrement, nous observons que dans le cas des systèmes effaçants, la décomposition produit un S vide (i.e toutes les règles peuvent être simulées et éliminées de R). Comme le système de Dyck est algébrique inverse, cela étend en effet le résultat de [HW 04] aux systèmes reconnaissables. En outre et contrairement à [HW 04], notre décomposition utilise uniquement un système algébrique élémentaire inverse, à savoir D. Notons cependant que de nombreux autres systèmes peuvent être directement décomposés en le système vide comme par exemple les systèmes de récriture préfixe (qui codent la relation de transition des systèmes à pile), leur variante bifixe, et les systèmes à gauche ou à droite. Dans le cas fini, la plupart de ces systèmes peuvent également être simulés par des systèmes effaçants, comme cela a été montré dans [HW 04].

Comme exemple, les systèmes multi-piles tels que ceux définis dans [BMT 05] peuvent être considérés comme des systèmes gauche-droite, et il en résulte que leur relation de transition préserve l’algébricité et que leur inverse préserve la régularité. Notre principale application concerne les systèmes marqués, qui généralisent les systèmes de récriture préfixe et suffixe. Etant donné un ensemble de symboles spéciaux appelés marques, que nous séparons en marques préfixes et marques suffixes, nous considérons des règles de la forme #u −→# ′ v, où #, #′ sont des marques préfixes et u ne contient aucun marque. Nous permettons également des règles suffixes, bifixes, et démarquées qui sont définies de façon similaire. Puisque v peut contenir des marques, cela étend strictement les notions antérieures des systèmes marqués définis dans [Al 08]. Si l’ensemble des règles marquées est reconnaissable et si l’ensemble des règles non marquées est algébrique, nous montrons que notre décomposition s’applique, et qu’il en résulte que la dérivation d’un tel système (resp. son inverse) préserve l’algébricité (resp. la régularité). Ce résultat est encore vrai lorsque nous ne séparons pas les marques en préfixes et suffixes, mais en imposant que les marques dans le membre gauche d’une règle soient celles de son membre droit. Ceci étend les propriétés connues de préservation des langages réguliers et algébriques pour des systèmes marqués plus simples [Al 08].

Décomposition de la dérivation

Dans ce paragraphe, nous nous focalisons sur la préservation de la régularité et de l’algébricité pour la dérivation des systèmes de récriture de mots. Après avoir analysé les résultats connus , nous généralisons la méthode de décomposition de la dérivation des systèmes effaçants [HW 04] à tous les systèmes de récriture de mots , ce qui nous permet d’obtenir de nouvelles sous-familles de systèmes préservant la régularité ou l’algébricité. Nous commençons par rappeler quelques définitions de base et nous introduisons quelques notations.

Notations

Pour simplifier, un singleton {x} est souvent identifié avec x. Pour tout ensemble E, nous écrivons |E| son cardinal, et 2E l’ensemble de ses parties. Une relation  binaire R d’un ensemble E dans un ensemble F est une partie de E×F. Toute couple (x,y) ∈ R est également désigné par xR y. L’inverse de R est la relation R−1 = { (y,x) | x R y}. Le domaine de R est l’ensemble Dom(R) = { x | ∃ y (x R y) } de ses premières composantes, et l’image de R est l’ensemble Im(R) = { y | ∃ x (x R y) } = Dom(R−1 ) de ses deuxièmes composantes. L’image par R d’un sous-ensemble P ⊆ E est R(P) = { y | ∃ x ∈ P (x R y) } ; en particulier, Im(R) = R(E) = R(Dom(R)). L’identité sur E est la relation IdE = { (x,x) | x ∈ E }. La composition de R ⊆ E×F avec S ⊆ F ×G est R o S = { (x,z) | ∃ y (x R y ∧ y S z) }.

Soit N un alphabet. Nous notons Alph(u) = { u(i) | 1 ≤ i ≤ |u| } l’ensemble des lettres d’un mot u ∈ N∗ . Ceci est étendu par union à tout langage P ⊆ N∗ : Alph(P) = { a | ∃ u ∈ P, a ∈ Alph(u) }. La concaténation de relations binaires R et S sur N∗ est R.S = { (ux,vy) | uR v ∧ xS y }, et la concaténation à gauche et à droite de R par un langage P ⊆ N∗ est R.P = R.IdP = { (uw,vw) | uR v ∧ w ∈ P } et P.R = IdP .R.

Un automate A sur E est un sous-ensemble A ⊆ Q×E×Q ∪ {ι,o}×Q où Q est l’ensemble de ses états et ι,o sont des symboles : on dit que p est une entrée pour (ι,p) ∈ A et que p est une sortie pour (o,p) ∈ A. Toute triplet (p,a,q) ∈ A est une transition étiquetée par a de l’état p à l’état q. Un automate A reconnaît l’ensemble L(A) des étiquettes de ses chemins acceptants : L(A) = { a1…an | n ≥ 0 ∧ ∃ p0,… ,pn (ι,p0),(p0,a1,p1),… ,(pn−1,an,pn),(o,pn) ∈ A }. Un langage régulier sur N est le langage reconnu par un automate fini étiqueté dans N (ou N∗ ). Une substitution h sur N est une relation binaire sur N∗ définie par l’image h(a) de chaque lettre a ∈ N, et qui est étendue par morphisme à tous les mots : h(a1…an) = h(a1)…h(an) pour tout entier n ≥ 0 et pour toutes lettres a1,…,an ∈ N. La substitution h est dite finie (resp. régulière) si h(a) est un langage fini (resp.régulier) pour toute lettre a ∈ N. Une relation reconnaissable R sur N∗ est une union finie de produits binaires de langages réguliers : R = U1×V1 ∪…∪Up×Vp pour p ≥ 0 et pour des langages réguliers U1,V1,… ,Up,Vp. Un transducteur A sur N est un automate étiqueté sur N∗×N∗ dont le langage est interprété comme une relation binaire, appelée relation rationnelle.

Décomposition

Dans ce paragraphe, nous reprenons le principe de décomposition de la proposition 11 pour définir une décomposition de la dérivation de tout système de récriture. Comme déjà esquissé au paragraphe précédent, l’application d’une règle de récriture simple (uv,w) à un mot x peut être simulée par l’insertion du facteur ←u w →v dans x, puis par la suppression des lettres fléchées en utilisant le système de Dyck. Nous nous servons de cette idée en identifiant les règles qui dans la dérivation peuvent être simulées par ce processus.

Table des matières

1 Introduction
2 Notions préliminaires
2.1 Grammaires de mots et langages
2.1.1 Mots et langages
2.1.2 Systèmes de récriture
2.1.3 Grammaires et hiérarchie de langages
2.2 Grammaires de graphes et langages
2.2.1 Graphes
2.2.2 Chemins
2.2.3 Graphes et langages
2.2.4 Isomorphisme de graphes
2.2.5 Grammaires de graphes
3 Grammaires de graphes et langages algébriques
3.1 Lemme des paires itérantes
3.1.1 Introduction
3.1.2 Lemme des paires itérantes
3.1.3 Démonstration géométrique du lemme des paires itérantes
3.2 Lemme de Parikh
3.2.1 Introduction
3.2.2 Lemme de Parikh
3.2.3 Démonstration géométrique du lemme de Parikh
4 Plus courts chemins
4.1 Calculs avec des grammaires de graphes
4.2 Algorithmes de calculs
4.3 Calculs sur des graphes réguliers
5 Régularité et algébricité des systèmes de récriture
5.1 Introduction
5.2 Décomposition de la dérivation
5.2.1 Notations
5.2.2 Propriétés de préservation
5.2.3 Décomposition
5.3 Applications
5.3.1 Systèmes préfixes, suffixes et bifixes
5.3.2 Dérivation gauche-droite
5.3.3 Systèmes marqués
6 Conclusion

Lire le rapport complet