Nominal Equational Rewriting and Narrowing

Mauricio Ayala-Rincón, Maribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida · 2025

Read Nominal Equational Rewriting and Narrowing by Mauricio Ayala-Rincón, 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-2506-05835.txt.

Introduction

Rewriting simplifies expressions by applying rules step by step. Narrowing goes further: it turns rewriting into a search for values that make an equation true. Both tools were built for simple first-order terms, and both run into trouble in languages with binders, where names and scopes matter. Mauricio Ayala-Rincón, Maribel Fernández, Daniele Nantes-Sobrinho, and Daniella Santaguida extend the machinery in 2025 to exactly that setting, using nominal techniques.

They give the first definitions of nominal rewriting and narrowing that work modulo an equational theory, such as commutativity, with name equivalence handled the right way. A property they call E-coherence pins down when normal forms behave as they should. Their E-Lifting theorem then guarantees that plain rewriting steps and narrowing steps match, which a correct unification method needs in order to be trusted. Commutativity is the running example.

Catalog record

CREATORMauricio Ayala-Rincón, Maribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-05835

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nominal Equational Rewriting and Narrowing Mauricio Ayala-Rincón, Maribel Fernández, Daniele Nantes-Sobrinho, Daniella Santaguida Abstract Narrowing is a well-known technique that adds to term rewriting mechanisms the required power to search for solutions to equational problems. Rewriting and narrowing are well-studied in first-order term languages, but several problems remain to be investigated when dealing with languages with binders using nominal techniques. Applications in programming languages and theorem proving require reasoning modulo α \alpha -equivalence considering structural congruences generated by equational axioms, such as commutativity. This paper presents the first definitions of nominal rewriting and narrowing modulo an equational theory. We establish a property called nominal 𝖤 \mathsf{E} -coherence and demonstrate its role in identifying normal forms of nominal terms. Additionally, we prove the nominal 𝖤 \mathsf{E} -Lifting theorem, which ensures the correspondence between sequences of nominal equational rewriting steps and narrowing, crucial for developing a correct algorithm for nominal equational unification via nominal equational narrowing. We illustrate our results using the equational theory for commutativity. 1 Introduction The nominal framework [ 16 ] has emerged as a promising approach for dealing with languages involving binders such as lambda calculus and first-order logic. In this framework, equality coincides with the \alpha -equivalence relation, denoted as \approx_{\alpha} , and freshness constraints are integrated within the nominal reasoning rather than being relegated to the meta-language. For example, the expression a\#M (“ a is fresh for M ”) indicates that if a name a occurs in a term M , it must be abstracted by some binder, such as the \lambda in the lambda calculus, or \exists,\forall -quantification in first-order logic, i.e., a cannot occur free in M . To enable reasoning within this framework, nominal unification [ 12 , 23 ] was developed and formalised in proof assistants such as Isabelle [ 23 ] , PVS [ 9 ] and Coq [ 5 ] . Nominal unification involves finding a substitution \sigma that solves the problem s\ _{?}{\overset{}{\approx}}_{?}\ t , meaning s\sigma\approx_{\alpha}t\sigma , where s and t are nominal terms. It is well-known that unification is fundamental for automated reasoning, serving as the foundation for resolution-based proof assistants, type inference, and numerous other applications. While these applications are anticipated to extend to nominal unification, substantial work is required to verify this. To pursue applications of the nominal framework, extensions of nominal unification with equational theories have been investigated. Initial efforts included integrating the theories of \mathsf{A} ssociativity ( \approx_{\alpha,\mathsf{A}} ), \mathsf{C} ommutativity ( \approx_{\alpha,\mathsf{C}} ) and \mathsf{A} ssociativity- \mathsf{C} ommutativity ( \approx_{\alpha,\mathsf{AC}} ) to \alpha -equality [ 5 ] . Various algorithms for nominal unification modulo commutativity ( \mathsf{C} -unification) and formalisations of their correctness in proof assistants PVS and Coq have been developed [ 2 , 3 , 8 , 6 ] . These development efforts reveal significant differences between first-order and nominal languages, such as the theory of \mathsf{C} -unification, which has nullary unification type if \alpha -equivalence is considered [ 2 ] , contrasting with the finitary type of first-order \mathsf{C} -unification [ 11 ] . Further investigations into nominal unification include exploring a letrec constructor and extensions involving atom variables [ 22 ] . Another example is the development of an algorithm for nominal \mathsf{C} -matching [ 4 ] , a special case of nominal \mathsf{C} -unification (dealing with problems s\ _{?}{\overset{\mathsf{C}}{\approx}}_{?}\ t where the substitution \sigma only applies in one side: s\sigma\approx_{\alpha,\mathsf{C}}t ). Recently, a naive nominal extension of the Stickel-Fages first-order \mathsf{AC} -unification algorithm introduced cyclicity in solutions produced by translations of unification problems to Diophantine systems as reported in [ 10 ] , and this differs from the original (first-order) approach which has a terminating algorithm. These developments underline the complexity of extending equational unification algorithms to the nominal framework, and new methods need to be proposed to obtain the desired extensions. An alternative approach to solving nominal unification problems modulo equational theories (i.e., nominal \mathsf{E} -unification problems), developed in [ 7 ] , involves the use of nominal narrowing 1 1 1 Roughly, nominal narrowing is a generalisation of nominal rewriting by using nominal unification instead of nominal matching in its definition. . This technique can be used when the equational theory \mathsf{E} is presented by a convergent nominal rewriting system [ 15 , 13 ] . Different extensions are needed for rewriting modulo \mathsf{E} when such a presentation is impossible. However, nominal techniques modulo an equational theory \mathsf{E} , and in particular, nominal \mathsf{E} -rewriting, remain unexplored. This work represents the first step towards developing nominal \mathsf{E} -techniques, when using a convergent nominal rewrite system equivalent to the theory \mathsf{E} is not possible. In first-order term languages [ 19 , 24 , 14 ] , the standard technique is to split a set of identities \mathsf{T} into a term rewriting system \mathsf{R} and an equational part \mathsf{E} , so that \mathsf{T}=\mathsf{R}{\cup}\mathsf{E} , considering the rewriting relation generated by \mathsf{R} on the equivalence classes of terms generated by \mathsf{E} . We propose extending this technique to nominal languages by adapting the notions of nominal rewriting [ 15 , 21 , 20 ] and nominal narrowing [ 7 ] to work modulo \mathsf{E} , incorporating the relation \approx_{\alpha,\mathsf{E}} . These extensions result in the first definitions of nominal \mathsf{R/E} -rewriting (Definition 3.1 ) and \mathsf{R,E} -rewriting (Definition 3.2 ) as well as \mathsf{E} -narrowing (Definition 3.8 ). Nominal \mathsf{R/E} -rewriting applies rules from \mathsf{R} in the equivalence class modulo \approx_{\alpha,\mathsf{E}} of a nominal term t , while \mathsf{R,E} -rewriting uses nominal \mathsf{E} -matching to determine if a rule in \mathsf{R} applies to a nominal term, say t . This nominal term t may have variables, thus the definition of the relations \mathsf{R/E} and \mathsf{R,E} also feature freshness conditions. We prove that it is possible to identify the normal form of a nominal term, say t , with respect to the relation \mathsf{R/E} (denoted t\downarrow_{\mathsf{R/E}} ) to the normal form of the same term, but with respect to the relation \mathsf{R,E} (that is, t\downarrow_{\mathsf{R,E}} ), when the relation \mathsf{R,E} has a property called nominal \mathsf{E} -coherence , whose extension from a corresponding property in first-order term language [ 18 ] is established here. Proving the correspondence between sequences of nominal \mathsf{R,E} -rewriting steps and \mathsf{E} -narrowing steps (Nominal \mathsf{E} -Lifting Theorem 4.6 ) is essential to develop an algorithm for nominal \mathsf{T} -unification via nominal \mathsf{E} -narrowing. Since the decidability of nominal \mathsf{T} -unification relies on the decidability of nominal \mathsf{E} -unification and \mathsf{E} -matching, and so far, the only equational theory for which a nominal unification algorithm exists is commutativity \mathsf{C} , a corollary of our developments is that the nominal \mathsf{C} -Lifting Theorem holds. Finally, due to the volume of extensions that were necessary to establish nominal \mathsf{E} -narrowing and rewriting, the final goal of using \mathsf{E} -narrowing as a sound and complete procedure for solving nominal \mathsf{T} -unification, remains ongoing work. Summarising, our main contributions are: 1. We extend the definitions and concepts regarding rewriting modulo \mathsf{E} to the nominal framework. For instance, we have nominal versions of the relations \to_{\mathsf{R,E}} and \to_{\mathsf{R/E}} for rewriting, and \rightsquigarrow_{\mathsf{R,E}} for nominal \mathsf{E} -narrowing. 2. We prove technical auxiliary results relating \to_{\mathsf{R,E}} and \to_{\mathsf{R/E}} . These required the

Read the complete text