A characterization of local confluence of conditional term rewriting systems





Publicado en

Actas de las XXI Jornadas de Programación y Lenguajes (PROLE 2022)


CC BY 4.0


When using non-deterministic reduction-based systems, guaranteeing that two diverging steps can be eventually rejoined is crucial for a faithful use in most applications. This property of reduction systems is called local confluence. Gérard Huet provided a characterization of local confluence for term rewriting systems. In conditional term rewriting systems, reduction steps may depend on the satisfaction of specific conditions in rules. Although conditional rewriting was introduced and used already in the 1970s and deeply investigated in the early 1980s, only partial characterizations or sufficient conditions of local confluence of conditional term rewriting have been obtained so far. In this paper, we char- acterize local confluence of conditional rewrite systems as the joinability of a set of conditional pairs including the usual conditional critical pairs and a new kind of pairs we call conditional variable pairs.


Acerca de Lucas, Salvador

Palabras clave

Automated Reasoning, Conditional Rewriting, Confluence, First-Order Logic, Program Analysis
Página completa del ítem
Notificar un error en este resumen
Mostrar cita
Mostrar cita en BibTeX
Descargar cita en BibTeX