inria-00515395, version 1
Infinite families of finite string rewriting systems and their confluence
Proc. LPAR 2010 (2010) missing
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).
- a – CEA
- 1 :
- INRIA – Tsinghua University / Beijing – LIAMA
- 2 :
- Domaine : Informatique/Logique en informatique
- Mots-clés : Recriture Parametrisation Confluence terminaison
- inria-00515395, version 1
- http://hal.inria.fr/inria-00515395
- oai:hal.inria.fr:inria-00515395
- Contributeur :
- Soumis le : Mardi 7 Septembre 2010, 10:41:22
- Dernière modification le : Mardi 7 Septembre 2010, 11:39:12




Documents associés
Exporter