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

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

Un problème central dans l’analyse de l’accessibilité d’un système R de récriture de mots est de déterminer l’ensemble ∗ −→ R (L) de tous les mots qui peuvent dériver selon R à partir de mots d’un langage L donné.

Bien que pour L fini, cet ensemble ∗ −→ R (L) ne soit pas en général récursif, divers travaux de recherche ont dégagé des familles générales de systèmes de récriture de mots dont la relation de dérivation ∗ −→ R a de bonnes propriétés de fermeture : elle préserve des classes générales de langages.

En particulier, on dit qu’un système R préserve la régularité (resp. l’algébricité) si, pour tout langage régulier (resp. algébrique) L, le langage ∗ −→ R (L) est aussi régulier (resp. algébrique). Onpeuttrouver 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. Notre construction est basée sur une observation simple que l’on va décrire.

Etant donné un mot u = a1…an, nous écrivons ←− u = ←− et −→ an …←− a1 et −→ u = −→ an …− → a1 où ←− a a sont de nouvelles lettres pour chaque lettre a d’origine. Pour tout système de récriture R et pour toute règle u → v de R, nous considérons les mots de la forme ←− u1v−→ − u2 avec u1u2 = u. Le sens implicite est que pour appliquer cette règle de récriture, le côté droit v peut être inséré à une certaine position i dans un mot à condition que u1 puisse être effacé à la gauche de la position i et u2 à la droite.

En d’autres termes, l’application de la règle u → v à un mot peut être simulée en insérant d’abord un des facteurs ← u←− u1v−→ u2 à une position appropriée, puis en effaçant les facteurs de la forme u ou−→ uu.

Cette procédure en deux phases peut être effectuée par une substitution suivie par l’application de règles algébriques inverses de la forme − → a a →εeta←− a → ε (constituant ce que nous appelons le système de récriture de Dyck, voir [KKO 06]). 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é