Infinite families of finite string rewriting systems and their confluence

Jean-Pierre Jouannaud 1 Benjamin Monate 2
1 FORMES - Formal Methods for Embedded Systems
LIAMA - Laboratoire Franco-Chinois d'Informatique, d'Automatique et de Mathématiques Appliquées, Inria Paris-Rocquencourt
Abstract : 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).
Type de document :
Communication dans un congrès
Fermüller and Voronkov. Proc. LPAR 2010, Oct 2010, Yogyakarta, Indonesia. SPRINGER, 2010, 17th International Conference on Logic for Programming, Artificial Intelligence and Reasoning
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00515395
Contributeur : Jean-Pierre Jouannaud <>
Soumis le : mardi 7 septembre 2010 - 10:41:22
Dernière modification le : mardi 17 avril 2018 - 11:28:03
Document(s) archivé(s) le : mardi 23 octobre 2012 - 15:40:33

Fichier

main-easychair.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00515395, version 1

Collections

INRIA | LIAMA | CIRAD | INRA | CEA | DRT | LIST

Citation

Jean-Pierre Jouannaud, Benjamin Monate. Infinite families of finite string rewriting systems and their confluence. Fermüller and Voronkov. Proc. LPAR 2010, Oct 2010, Yogyakarta, Indonesia. SPRINGER, 2010, 17th International Conference on Logic for Programming, Artificial Intelligence and Reasoning. 〈inria-00515395〉

Partager

Métriques

Consultations de la notice

258

Téléchargements de fichiers

108