💻 computer science

Towards an HRS Category in TermCOMP

The paper establishes a formal foundation for a new HRS subcategory in TermCOMP by proving that rewriting under Nipkow's HRSs and a beta-first strategy coincide for a specific syntactic subclass of higher-order benchmarks, thereby enabling more tools to compete in termination analysis.

Original authors: Johannes Niederhauser, Aart Middeldorp

Published 2026-06-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Johannes Niederhauser, Aart Middeldorp

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive international cooking competition called TermCOMP. The goal of this competition is to see which computer program (or "chef") is best at proving that a specific set of recipe instructions will eventually stop cooking and produce a final dish, rather than getting stuck in an infinite loop of stirring.

For years, this competition has had a specific category for "High-Order Cooking." However, there was a problem: the chefs were using different languages and different rules for how ingredients could be mixed. Some chefs followed Rule Set A (called AFSs), while others wanted to follow Rule Set B (called HRSs, based on the work of Nipkow). Because the rules were so different, the chefs couldn't really compete against each other fairly. It was like trying to compare a chef who only uses a whisk to a chef who only uses a blender; they are both making food, but the mechanics are too different to judge who is faster or better.

The Problem: Two Different Languages

In the world of computer science, these "recipes" are mathematical rules for rewriting symbols.

Rule Set A (AFSs) is like a strict kitchen where you can only swap ingredients if they match exactly. If a recipe says "add flour," you can't add "flour mixed with milk" unless you explicitly write that down.
Rule Set B (HRSs) is more flexible. It allows for "beta-reduction," which is like automatically simplifying a complex instruction. If a recipe says "take the result of mixing X and Y," HRSs let you immediately do the mixing and use the result, whereas Rule Set A might make you wait until the very end.

The authors of this paper, Johannes Niederhauser and Aart Middeldorp, wanted to create a fair playing field where chefs using Rule Set B could compete in the same arena as those using Rule Set A.

The Solution: A New "Universal Translator"

The paper introduces a new, carefully defined subset of recipes called Extended Pattern Rewrite Systems (EPRSs). Think of this as a special "Universal Translator" format.

The authors didn't just say, "Let's just let everyone use HRSs." Instead, they found a specific, simple way to write these flexible HRS recipes so that they could be understood by the existing competition system (which uses a format called STMRS).

They discovered a "sweet spot" of recipes where:

The Rules are Strict but Smart: They defined a class of recipes where the "left-hand side" (the part of the recipe being matched) follows a specific pattern called an "Extended Pattern." This ensures that when you try to match ingredients, the computer doesn't get confused or stuck.
The Translation Works Perfectly: They proved mathematically that if you take a recipe written in this new "Universal Translator" format (EPRS) and run it through the existing competition system (STMRS), the result is exactly the same as if you ran it using the original, more complex HRS rules.

The "Magic Trick" Analogy

Imagine you have a complex magic trick (the HRS rule) that involves a rabbit appearing out of a hat.

The Old Way: To prove the trick works, you had to build a whole new stage just for that specific rabbit.
The New Way: The authors showed that if you arrange the rabbit, the hat, and the wand in a very specific, simple way (the "well-behaved" EPRS), you can perform the exact same magic trick using the standard stage already built for the competition (the STMRS).

They proved that every time the HRS chef does a step, the STMRS chef can do a step followed by a quick "cleanup" (called $\beta$ -normalization) and end up with the exact same result.

Why This Matters

This isn't just about math; it's about fairness and progress.

More Chefs, More Competition: By defining this specific subset, the competition organizers can now invite more tools (chefs) that use the HRS style to compete.
Better Benchmarks: It allows the competition database (TPDB) to include a wider variety of problems without breaking the rules of the game.
Proven Equivalence: The paper doesn't just guess that this works; it provides a rigorous mathematical proof (Theorem 15) that the two methods are equivalent for this specific class of problems.

The Bottom Line

The authors successfully built a bridge between two different ways of thinking about computer rewriting. They showed that by restricting the rules just a little bit (using "well-behaved" patterns), you can make the flexible HRS style work perfectly within the existing TermCOMP framework. This lays the formal groundwork for a new, fair sub-category in the competition where more powerful tools can finally compete against each other.

Note: The paper focuses entirely on the mathematical foundation of this equivalence. It does not discuss specific real-world applications like medical diagnosis or clinical uses, nor does it predict future technologies beyond the scope of the competition itself. It is purely about making the "cooking competition" for computer proofs more inclusive and rigorous.

Technical Summary: Towards an HRS Category in TermCOMP

Problem Statement
The annual Termination Competition (TermCOMP) includes a category for higher-order rewriting. Historically, this category has utilized the semantics of Algebraic Functional Systems (AFSs), which rely on plain matching and explicit $\beta$ -reduction rules. While Nipkow's Higher-Order Rewrite Systems (HRSs), which perform rewriting modulo $\beta\eta$ and typically use Miller's patterns (PRSs) or the more recent Deterministic Higher-Order Pattern Rewrite Systems (DPRSs), are well-established formalisms, they have not been fully integrated into TermCOMP's competitive framework. The challenge lies in reconciling the semantics of HRSs (rewriting modulo $\beta\eta$ ) with the existing TermCOMP framework (based on AFSs and meta-substitutions) to allow tools targeting HRSs to compete directly against those targeting AFSs.

Methodology
The authors propose a formal bridge between HRSs and the current TermCOMP higher-order semantics, defined as Simply-Typed Meta-Substitution Rewrite Systems (STMRSs). The methodology involves three main steps:

Generalization of Patterns: The authors introduce Extended Pattern Rewrite Systems (EPRSs), a subclass of HRSs that generalizes both PRSs and DPRSs. EPRSs utilize "Extended Patterns" (EPATs), which relax the deterministic matching constraints of DPRSs while maintaining a structure where free variables are applied to non-abstraction arguments. This class is defined primarily to facilitate the theoretical proof rather than as a standalone practical tool.
Extension of STMRS Semantics: The authors extend the definition of STMRS rules (the current TermCOMP standard) to allow left-hand sides to be EPATs rather than just standard patterns. They introduce the concept of well-behaved and quasi-well-behaved terms. These syntactic restrictions ensure that when meta-substitutions are applied, the resulting terms remain in $\beta$ -normal form (specifically $\beta\eta$ -long normal form) without generating new $\beta$ -redexes that would require additional reduction steps.
Implementation via Normalized Rewriting: The core technical contribution is establishing that rewriting in a well-behaved STMRS, followed by $\beta$ -normalization, simulates rewriting in the corresponding EPRS. The authors define a translation between ordinary substitutions (used in EPRSs) and meta-substitutions (used in STMRSs) to prove that the two systems are equivalent regarding termination.

Key Contributions

Definition of EPRSs: A new syntactic subclass of HRSs that generalizes DPRSs, allowing for a broader range of benchmarks while retaining manageable matching properties.
Syntactic Restrictions for Equivalence: The introduction of "well-behaved" STMRS rules. These rules restrict left-hand sides to be well-behaved and right-hand sides to be quasi-well-behaved. This ensures that the application of meta-substitutions does not create $\beta$ -redexes, preserving the $\beta$ -normal form of terms.
Formal Equivalence Theorem: The paper proves that for a well-behaved STMRS $R$ and a term $s$ in $\beta\eta$ -long normal form, a rewrite step in the EPRS semantics ( $s \to_R t$ ) occurs if and only if a rewrite step in the STMRS semantics followed by $\beta$ -normalization occurs ( $s \Rightarrow_R \cdot \Rightarrow!_\beta t$ ).

Results
The primary result is Theorem 15, which establishes the correspondence between the rewrite relations of well-behaved STMRSs and their corresponding EPRSs. Specifically:

$s \Rightarrow_R \cdot \Rightarrow!_\beta t$ if and only if $s \to_R t$ (viewing $R$ as an EPRS).
This leads to Corollary 20, which states that termination of the strategy "rewrite then $\beta$ -normalize" in a well-behaved STMRS coincides with the universal termination of the corresponding EPRS.

The authors demonstrate that this equivalence holds for terms in $\beta\eta$ -long normal form. They note that for second-order STMRSs, the correspondence is even stronger, offering a one-to-one mapping between steps because meta-substitutions cannot create $\beta$ -redexes in that specific context.

Significance
The paper claims to lay the formal foundation for an HRS (sub)category in TermCOMP. By defining a syntactically checkable subset of benchmarks (well-behaved STMRSs) within the existing TPDB format, the authors enable:

Direct Competition: Tools designed for HRSs (using $\beta\eta$ -rewriting) can now compete against tools designed for AFSs within the same category, as their termination properties are proven to coincide under the proposed semantics.
Broader Tool Support: The implementation result allows for the comparison of properties beyond just termination, as the simulation is based on step-by-step correspondence rather than just a global termination property.
Refinement of Existing Work: The result strengthens previous implementations of PRSs in AFSMs (Kop) and combinatory systems (van Oostrom and van Raamsdonk) by extending them to a more general class of HRSs (EPRSs) and providing a rigorous proof for the equivalence of normalized rewriting and higher-order rewriting.

The authors remain modest regarding the scope, acknowledging that the result does not cover all HRSs because meta-substitution is strictly less powerful than full higher-order substitution. However, they argue that the defined subclass is sufficient to accommodate a significant portion of existing benchmarks and the specific DPRSs introduced in their prior work.