<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Resumen:
Local confluence of conditional and generalized term rewriting systems

Cargando...
Miniatura

Editor

Sistedes

Publicado en

Actas de las XXIII Jornadas de Programación y Lenguajes (PROLE 2024)

Licencia Creative Commons

Excepto donde se indique lo contrario, la licencia de este ítem se describe como CC BY-NC-ND 4.0

Resumen

Reduction-based systems are used as a basis for the implementation of programming languages, automated reasoning systems, mathematical analysis tools, etc. In such inherently non-deterministic systems, guaranteeing that diverging steps can be eventually rejoined is crucial for a faithful use in most applications. This property of reduction systems is called local confluence. In a landmark 1980 paper, Gérard Huet characterized local confluence of a Term Rewriting System as the joinability of all its critical pairs. In this paper, we characterize local confluence of Conditional Term Rewriting Systems, where reduction steps may depend on the satisfaction of specific conditions in rules: a conditional term rewriting system is locally confluent if and only if (i) all its conditional critical pairs and (ii) all its conditional variable pairs (which we introduce in this paper) are joinable. Furthermore, the logic-based approach we follow here is well-suited to analyze local confluence of more general reduction-based systems. We exemplify this by (i) including (context-sensitive) replacement restrictions in the arguments of function symbols, and (ii) allowing for more general conditions in rules. The obtained systems are called Generalized Term Rewriting Systems. A characterization of local confluence is also given for them.

Descripción

Acerca de Lucas, Salvador

Citación

Lucas, S.: Local confluence of conditional and generalized term rewriting systems. In: Arias, J. (ed.) Actas de las XXIII Jornadas de Programación y Lenguajes (PROLE 2024). Sistedes (2024). https://hdl.handle.net/11705/PROLE/2024/14