The Computability Path Order for Beta-Eta-Normal Higher-Order Rewriting (Full Version)

Johannes Niederhauser (🖂), Aart Middeldorp · 2025

Read The Computability Path Order for Beta-Eta-Normal Higher-Order Rewriting (Full Version) by Johannes Niederhauser (🖂), Aart Middeldorp (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-20121.txt.

Introduction

Johannes Niederhauser and Aart Middeldorp extend a termination proof tool for higher order rewriting to work on normal forms, in work from twenty twenty-five. Rewriting systems replace terms by rules, and proofs that they always stop are key for trust. Matching under beta and eta rules adds hard twists.

The new order, called NCPO, handles systems where its cousin tool fails, even when that cousin is paired with a strong transform trick. The authors argue that NCPO is far easier to automate with SAT and SMT solvers. Their prototype is the first to automate both NCPO and the older order with its transform. Worked examples show the order in action. The paper is the full version of the study.

Catalog record

CREATORJohannes Niederhauser (🖂), Aart Middeldorp
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

The Computability Path Order for Beta-Eta-Normal Higher-Order Rewriting (Full Version) Johannes Niederhauser (🖂), Aart Middeldorp Abstract We lift the computability path order and its extensions from plain higher-order rewriting to higher-order rewriting on β ​ η \beta\eta -normal forms where matching modulo β ​ η \beta\eta is employed. The resulting order NCPO is shown to be useful on practical examples. In particular, it can handle systems where its cousin NHORPO fails even when it is used together with the powerful transformation technique of neutralization. We also argue that automating NCPO efficiently is straightforward using SAT/SMT solvers whereas this cannot be said about the transformation technique of neutralization. Our prototype implementation supports automatic termination proof search for NCPO and is also the first one to automate NHORPO with neutralization. 1 Introduction Higher-order rewriting is known for its abundance of different formalisms where it is often unclear whether results for a particular notion of higher-order rewriting can be transferred to other kinds of higher-order rewriting [ 12 ] . In this paper, we are only concerned with one particular formalism, namely a slightly modified version of the higher-order rewrite systems (HRSs) à la Nipkow [ 16 ] . However, as the goal of this paper is to lift a particular termination method from one formalism to another, a short discussion about differences and similarities of the used formalisms is necessary. First and foremost, when we talk about higher-order rewriting in this paper, we mean the particular flavor of higher-order rewriting which considers terms of the simply-typed lambda calculus as objects to be rewritten. Within this class of higher-order rewrite formalisms, we further distinguish between plain and normal higher-order rewriting: Plain higher-order rewriting uses plain syntactic matching and views lambda calculus’ \beta -reduction as a proper rewrite rule which has to be oriented for termination. On the other hand, normal higher-order rewriting uses matching modulo \beta\eta , which means that terms which are \beta\eta -equivalent should also be equivalent with respect to the reduction order that is used for establishing termination. Nipkow’s HRSs are a premier example of normal higher-order rewriting. HRSs are an interesting formalism for automated reasoning as they can directly represent the terms of higher-order logic and as such are part of the meta-theory of interactive theorem provers like Isabelle [ 20 ] . Furthermore, they come with a critical pair lemma [ 16 ] which is vital for automated equational reasoning with techniques such as completion [ 7 ] . In particular, automated confluence analysis of higher-order rewriting typically uses HRSs, as witnessed in the Confluence Competition (2015--2020). 1 1 1 https://project-coco.uibk.ac.at/ While many termination methods are available for plain higher-order rewriting [ 10 , 12 , 2 ] , the situation for normal higher-order rewriting is different. For a long time, powerful termination methods for HRSs were only based on van de Pol’s results [ 21 ] which employ the monotone algebra approach [ 24 ] , i.e., semantic termination arguments which are difficult to automate except for more specialized cases like polynomial interpretations of fixed shape [ 5 ] . An early version of the higher-order recursive path order (HORPO) which is designed for plain higher-order rewriting was adapted for the important subclass of pattern HRSs in [ 22 ] , an implementation of this approach is available in the tool CSI^ho [ 19 ] . Furthermore, the formalism of algebraic functional systems with meta-variables (AFSMs) captures both plain and normal rewriting and therefore makes a larger number of termination methods available for HRSs [ 12 ] . An implementation of these methods is available in the tool WANDA [ 13 ] . However, WANDA has not been optimized for HRSs and the theory developed around it only establishes termination for systems where all left-hand sides are patterns [ 17 ] . A powerful recursive path order specifically designed for HRSs and without the restriction to patterns as left-hand sides of rules was missing until Jouannaud and Rubio lifted their definite version of HORPO [ 10 ] from plain to normal higher-order rewriting, resulting in NHORPO [ 11 ] . However, the important extension of HORPO by the computability closure [ 10 ] is not considered. Instead, a novel transformation technique named neutralization is introduced. Its goal is to simplify a given system with respect to the applicability of NHORPO without affecting the system’s termination behavior. The aim of this paper is to develop a syntax-directed reduction order for normal higher-order rewriting which is sufficiently powerful compared to NHORPO with neutralization but easier to automate using SAT/SMT solvers. Our starting point is the computability path order (CPO) [ 2 ] which is defined for plain higher-order rewriting. CPO is an extension of HORPO which incorporates computability closure [ 3 ] in a sophisticated way. We follow the general approach from [ 11 ] to lift the extension of core CPO with accessible subterms and small symbols to HRSs, resulting in the \beta\eta -normal computability path order (NCPO). In particular, we will show that there are HRSs which NCPO can prove terminating but where NHORPO (with or without neutralization) as well as the HORPO implementations in WANDA [ 13 ] and CSI^ho [ 19 ] fail. In designing a reduction order for normal higher-order rewriting, one has to deal with the well-known problems that well-founded orders which are compatible with \beta\eta cannot be monotone (closed under contexts) and stable (closed under substitutions) in general as the following examples show: Example 1 Consider \mathsf{a}>\mathsf{b} . If > is closed under contexts, we should also have (\lambda y.\mathsf{c})\mathsf{a}>(\lambda y.\mathsf{c})\mathsf{b} . If we also want > to be compatible with \beta\eta , we obtain \mathsf{c}>\mathsf{c} which means that > cannot be well-founded. Now consider Fx>x . If > is closed under substitutions, we should also have (\lambda x.x)\mathsf{a}>\mathsf{a} . If we also want > to be compatible with \beta\eta , we obtain \mathsf{a}>\mathsf{a} which again means that > cannot be well-founded. In [ 21 ] , van de Pol models substitutions via contexts using \beta -reduction, thereby eliminating the second problem. For the first problem, two different orders >_{1} and >_{2} are introduced and it is shown that s>_{1}t implies C[s]>_{2}C[t] for all terms s , t and contexts C . Since the relations between >_{1} and >_{2} are intrinsically semantic, it is not clear how this approach can be transferred to path orders. In [ 11 ] , both problems were solved by restricting the order > to \beta\eta -normal forms and layering it with its plain version ( \sqsupset ) in a way such that s>t implies s\sigma{\downarrow}\sqsupset^{+}t\sigma{\downarrow} for all substitutions \sigma where s{\downarrow} denotes the \beta\eta -normal form of a term s . Then, monotonicity and well-foundedness of the plain version can be used in order to show that (>,\sqsupset) is a reduction order. We will utilize this approach in order to define a reduction order (>,\sqsupset) where > is NCPO and \sqsupset is CPO. The remainder of this paper is structured as follows. Section 2 introduces the basic concepts including the type of higher-order rewriting which we are concerned with in this paper as well as an appropriate notion of \beta\eta -normal higher-order reduction orders. Section 3

Read the complete text