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
| CREATOR | Ali K. Caires-Santos, Maribel Fernández, Daniele Nantes-Sobrinho |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 237 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19287