Infinite families of finite string rewriting systems and their confluence - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Infinite families of finite string rewriting systems and their confluence

Résumé

We introduce parameterized rewrite systems for describing infinite families of finite string rewrite systems depending upon non-negative integer pa- rameters, as well as ways to reason uniformly over these families. Unlike previous work, the vocabulary on which a rewrite system in the family is built depends it- self on the integer parameters. Rewriting makes use of a toolkit for parameterized words which allows to describe a rewrite step made independently by all systems in an infinite family by a single, effective parameterized rewrite step. The main result is a confluence test for all systems in a family at once, based on a critical pair lemma classically based on computing finitely many overlaps between left- hand sides of parameterized rules and then checking for their joinability (which decidability is not garanteed).
Fichier principal
Vignette du fichier
main-easychair.pdf (157.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00515395 , version 1 (07-09-2010)

Identifiants

  • HAL Id : inria-00515395 , version 1

Citer

Jean-Pierre Jouannaud, Benjamin Monate. Infinite families of finite string rewriting systems and their confluence. Proc. LPAR 2010, Steffen Hölldobler, Oct 2010, Yogyakarta, Indonesia. ⟨inria-00515395⟩
177 Consultations
138 Téléchargements

Partager

Gmail Facebook X LinkedIn More