Towards an HRS Category in TermCOMP
Johannes Niederhauser, Aart Middeldorp · 2026
Read Towards an HRS Category in TermCOMP by Johannes Niederhauser, Aart Middeldorp (2026) 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-2606-25448.txt.
Introduction
Termination provers compete yearly in TermCOMP, but its higher order category has always used one rewriting semantics, leaving another major formalism without a proper arena. Johannes Niederhauser and Aart Middeldorp lay the formal groundwork for changing that in 2026. Higher order rewrite systems, defined by Nipkow, rewrite terms modulo beta and eta steps, unlike the algebraic functional systems the competition currently scores. The question is whether the two semantics ever agree without extra machinery.
For a simple syntactically defined subclass of the benchmark database, the pair proves they do coincide: rewriting under the higher order systems matches a beta first strategy under the existing semantics. That equivalence is exactly what an HRS subcategory needs to be meaningful. More tools could then compete head to head on higher order termination problems.
Catalog record
| CREATOR | Johannes Niederhauser, Aart Middeldorp |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25448
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Towards an HRS Category in TermCOMP Johannes Niederhauser, Aart Middeldorp Abstract We show that there is a simple syntactically-defined subclass of higher-order benchmarks in the termination problem database for which rewriting according to Nipkow’s higher-order rewrite systems (HRSs) and rewriting according to a beta-first strategy in the semantics of TermCOMP’s higher-order category coincide. This lays the formal foundation for an HRS (sub)category in TermCOMP which would allow more tools to compete against each other. University of Innsbruck, Innsbruck, Austria [email protected]://orcid.org/0000-0002-8662-6834 University of Innsbruck, Innsbruck, Austria [email protected]://orcid.org/0000-0001-7366-8464 We thank Cynthia Kop as well as the anonymous reviewers for their valuable and extensive feedback. ccs Theory of computation Equational logic and rewriting ccs Theory of computation Lambda calculus keywords higher-order rewriting, termination † † runningauthor: J. Niederhauser and A. Middeldorp † † copyright: Johannes Niederhauser and Aart Middeldorp † † corref: result † † corref: result 1 Introduction Higher-order rewriting comes in many different flavors. Popular choices include Jouannaud and Okada’s algebraic functional systems (AFSs) [ 6 , 7 ] and higher-order rewrite systems (HRSs) as defined by Wolfram and Nipkow [ 19 , 12 ] . Both formalisms consider terms of the simply-typed \lambda -calculus. AFSs use plain matching and augment the rewrite system with a dedicated rule for \beta -reduction whereas HRSs perform rewriting modulo \beta\eta . In order to keep the matching problem and therefore rewriting with HRSs manageable, left-hand sides are typically restricted to Miller’s patterns (PATs) [ 13 ] , resulting in the subclass of pattern rewrite systems (PRSs) [ 12 ] . Recently, we introduced another subclass of HRSs by extending PRSs to deterministic higher-order pattern rewrite systems (DPRSs) [ 14 ] . DPRSs use Yokoyama et al.’s deterministic higher-order patterns (DHPs) as left-hand sides. Like PATs, DHPs enjoy a deterministic matching problem of linear complexity [ 20 ] . Since 2010, a category for higher-order rewriting has been part of the annual international termination competition (TermCOMP). 1 1 1 https://termination-portal.org/wiki/Termination_Competition Except for a demonstration category for HRSs in 2018, the higher-order category has always considered AFS semantics. In 2024, the termination problem database (TPDB) was ported to the new ARI format which is also used in the confluence competition. 2 2 2 https://project-coco.uibk.ac.at/ A discussion about the higher-order format ensued, and a proposal by Kop was implemented. 3 3 3 https://github.com/orgs/TermCOMP/discussions/86 This year, TermCOMP provides a reference describing the syntax and semantics of its categories for the first time [ 5 ] . In that document, Kop defines the semantics of the higher-order category as a restricted version of her algebraic functional systems with meta-variables (AFSMs) [ 10 ] which we shall refer to as simply-typed meta-substitution rewrite systems (STMRSs). The definition of STMRSs is given such that other popular flavors of higher-order rewriting can be accommodated easily. A subcategory for AFSs is established by simply restricting the eligible benchmarks. For PRSs, Kop defines a restricted class of STMRSs where termination of the strategy which prefers \beta -reduction coincides with universal termination of the corresponding PRS. This idea is based on a result in Kop’s PhD thesis [ 10 , Theorem 3.5] . In this paper, we extend STMRSs such that they can model a more general class of HRSs including our DPRSs. To that end, we introduce the ad-hoc definition of extended pattern rewrite systems (EPRSs) which constitute a generalization of DPRSs where we do not enforce deterministic matching. EPRSs are not meant to be useful in their own right, but they simplify the development in this paper and allow us to focus on the properties of DPRSs which are needed in order to obtain our main goal. Instead of just proving the relationship between EPRSs and STMRSs with respect to termination, we show that any step in an EPRS can be modeled by a step followed by \beta -normalization in STMRSs. This implementation result lays the foundation for comparing also other properties besides termination. Furthermore, our result extends and strengthens similar results in the literature such as Kop’s implementation of PRSs in AFSMs [ 10 , Section 3.3] as well as van Oostrom and van Raamsdonk’s implementation of PRSs in Klop’s combinatory systems with explicit \beta [ 17 ] . 2 Preliminaries In this paper, we consider rewrite systems over simply-typed \lambda -terms [ 4 , 2 ] . Given a set of sorts \mathcal{S} ( \iota , \kappa ), 4 4 4 This means that in the remainder, \iota and \kappa are used exclusively to represent arbitrary sorts. We will continue to define naming conventions in this fashion. the set of simple types \mathcal{T} ( \sigma , \tau ) is defined as \mathcal{S}\subseteq\mathcal{T} and \sigma\to\tau\in\mathcal{T} whenever \sigma,\tau\in\mathcal{T} . We follow the usual convention that \to is right-associative, so all types can be denoted in a form \sigma_{1}\to\cdots\to\sigma_{n}\to\iota . We assume an infinite set of typed variables \mathcal{V} ( x , y , z , w ) such that there are infinitely many variables of every type as well as a signature \mathcal{F} ( f , g ) consisting of typed function symbols disjoint from \mathcal{V} . A head ( h ) is either a variable or a function symbol. We write h:\sigma\in\mathcal{F} ( h:\sigma\in\mathcal{V} ) if h is a head of type \sigma . If this information is not important, we sometimes omit the type and just write h\in\mathcal{F} ( h\in\mathcal{V} ). The set \Lambda_{\sigma} of simply-typed \lambda -terms ( s , t , u , v ) of type \sigma is defined inductively together with the set H_{\sigma} of head-terms of type \sigma : • h\in H_{\sigma} if h:\sigma\in\mathcal{F}\cup\mathcal{V} , • \lambda x.s\in H_{\tau\to\sigma} if x:\tau\in\mathcal{V} and s\in\Lambda_{\sigma} , and • st_{1}\cdots t_{n}\in\Lambda_{\sigma} if s\in H_{\tau_{1}\to\cdots\to\tau_{n}\to\sigma} and t_{i}\in\Lambda_{\tau_{i}} for 1\leqslant i\leqslant n . We obtain H_{\sigma}\subseteq\Lambda_{\sigma} by setting n=0 in the final case above. This presentation of (simply-typed) \lambda -terms is due to Wadsworth; a formal justification is given in [ 3 , Lemma 8.3.7] . If s\in\bigcup_{\sigma\in\mathcal{T}}\Lambda_{\sigma} we say that s is a term . We abbreviate \lambda x_{1}.\dots\lambda x_{n}.s to \lambda x_{1},\dots,x_{n}.s and denote the set of free variables of a term s by \mathsf{FV}(s) . A variable x is fresh for a term s if x\notin\mathsf{FV}(s) . The proper subterm relation is defined as follows: \lambda x.s\vartriangleright u if s\trianglerighteq u and st_{1}\cdots t_{n}\vartriangleright u if t_{i}\trianglerighteq u for some 1\leqslant i\leqslant n . Here, {\trianglerighteq}={\vartriangleright}\cup{=} . If s\trianglerighteq t we say that t is a subterm of s . A context ( C ) is a term containing exactly one occurrence of the special symbol \square which can assume any type. We write C[s] to denote the term where \square has been replaced by the term s of the same type. Finite mappings from variables to terms of the same type are called substitutions ( \gamma ). Given a substitution \gamma=\{\hskip 0.85358ptx_{1}\mapsto s_{1},\,\dots,\,x_{n}\mapsto s_{n}\hskip 0.85358pt\} we define \mathcal{D}\mathsf{om}({\gamma})=\{\hskip 0.85358pt{x_{1}},\dots,{x_{n}}\hskip 0.85358pt\} , \mathcal{I}\mathsf{m}({\gamma})=\{\hskip 0.85358pt{s_{1}},\dots,{s_{n}}\hskip 0.85358pt\} and \mathsf{FV}(\gamma)=\bigcup_{i=1}^{n}\mathsf{FV}(s_{i}) . We say that a variable x is fresh for a substitution \gamma if x\notin\mathcal{D}\mathsf{om}({\gamma})\cup\mathsf{FV}(\gamma) . By \gamma|_{V} we denote the restriction of \gamma such that \mathcal{D}\mathsf{om}({\gamma|_{V}})=\mathcal{D}\mathsf{om}({\gamma})\cap V . Given a term s and a substitution \gamma , its application s\gamma binds stronger than the abstraction operator and is defined by