Extending Higher-Order Critical Pairs

arXiv:2610.38576 · cs.LO · Submitted 2026-10-28 · Read on arXiv

cs.LO

Submitted: 2026-10-28

Updated: 2026-10-28

License: http://creativecommons.org/licenses/by/4.0/

The gist: Confluence is a fundamental property of computation which implies that the nondeterminism of a system does not affect its outcomes.

Abstract

Confluence is a fundamental property of computation which implies that the nondeterminism of a system does not affect its outcomes. A key concept of confluence research in rewriting theory is the notion of critical pairs which captures the potential local sources of non-confluence. In this paper, we lift the definition of higher-order critical pairs to a more expressive class of higher-order rewrite systems. Thereby, we facilitate confluence analysis of rewrite systems which can express complex one-step computations as well as program transformations from functional programming.

Related papers