Nominal Equational Narrowing: Rewriting for Unification in Languages with Binders

Maribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida · 2025

Read Nominal Equational Narrowing: Rewriting for Unification in Languages with Binders by Maribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida (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-2505-14895.txt.

Description

Maribel Fernández, Daniele Nantes-Sobrinho, and Daniella Santaguida build in 2025 a nominal rewriting frame for languages with binders. Rewriting with search, called narrowing, solves equation problems in term systems. Bound names, freshness rules, and axioms like commutation break first-order tools in that setting.

Their frame bakes renaming and freshness into the rules from the start. A coherence trait names when normal forms agree under renaming and axioms. A lifting theorem then links rewriting and narrowing paths in the nominal world. A unification method built on narrowing gains a proof of correctness.

Catalog record

CREATORMaribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14895

Browse the full library · About the Tower of Babel