148 articles – 163 Notices  [english version]

inria-00515395, version 1

Infinite families of finite string rewriting systems and their confluence

Jean-Pierre Jouannaud () 1, Benjamin Monate () a2

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 :  FORMES (LIAMA)
  • INRIA – Tsinghua University / Beijing – LIAMA
  • 2 :  Laboratoire d'Intégration des Systèmes et des Technologies (LIST)
  • Domaine : Informatique/Logique en informatique
  • Mots-clés : Recriture Parametrisation Confluence terminaison
 
  • inria-00515395, version 1
  • 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