Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/inria-00515395
Contributor : Jean-Pierre Jouannaud Connect in order to contact the contributor
Submitted on : Tuesday, September 7, 2010 - 10:41:22 AM
Last modification on : Thursday, February 17, 2022 - 10:08:03 AM
Long-term archiving on: : Tuesday, October 23, 2012 - 3:40:33 PM

File

main-easychair.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00515395, version 1

Collections

CIRAD | CEA | CNRS | INRIA | INRA | LIAMA | DRT | INRIA2 | LIST | INRAE | ANR

Citation

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⟩

Share

Metrics

Record views

167

Files downloads

126