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).
Domaines
Logique en informatique [cs.LO]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...