Equational Reasoning Modulo Commutativity in Languages with Binders

Ali K. Caires-Santos, Maribel Fernández, Daniele Nantes-Sobrinho · 2025

Read Equational Reasoning Modulo Commutativity in Languages with Binders by Ali K. Caires-Santos, Maribel Fernández, Daniele Nantes-Sobrinho (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19287.txt.

Description

Ali Caires-Santos, Maribel Fernández, and Daniele Nantes-Sobrinho build a cleaner logic for reasoning about languages with binders and commutative operators. Their work appeared in twenty twenty-five. Binders, like quantifiers, tie names to scopes, and swapping tied names must not change meaning.

The team works in the nominal framework, which handles names and renaming directly. They swap the usual freshness side conditions for fixed-point constraints on permutations. Commutativity then folds smoothly into judgments about when two terms count as the same. They prove the system's key properties and give it a full semantics. They also present a matching algorithm that always ends and stays finite, unlike older approaches. The frame supports induction over such syntax.

Catalog record

CREATORAli K. Caires-Santos, Maribel Fernández, Daniele Nantes-Sobrinho
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE237 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-19287

Browse the full library · About the Tower of Babel