💻 computer science

Towards an HRS Category in TermCOMP

Het artikel legt een formeel fundament voor een nieuwe HRS-subcategorie in TermCOMP door te bewijzen dat herschrijven onder Nipkows HRS'en en een beta-first strategie samenvallen voor een specifieke syntactische deelklasse van hogere-orde benchmarks, waardoor meer tools in staat worden gesteld om te concurreren in terminatieanalyse.

Oorspronkelijke auteurs: Johannes Niederhauser, Aart Middeldorp

Gepubliceerd 2026-06-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Johannes Niederhauser, Aart Middeldorp

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme internationale kookwedstrijd organiseert genaamd TermCOMP. Het doel van deze wedstrijd is om te zien welke computerprogramma (of "chef") het beste is in bewijzen dat een specifieke set receptinstructies uiteindelijk zal stoppen met koken en een eindgerecht zal produceren, in plaats van vast te komen zitten in een oneindige lus van roeren.

Jarenlang heeft deze wedstrijd een specifieke categorie voor "High-Order Cooking" gehad. Echter, er was een probleem: de chefs gebruikten verschillende talen en verschillende regels voor hoe ingrediënten gemengd konden worden. Sommige chefs volgden Regelset A (genaamd AFSs), terwijl anderen de voorkeur gaven aan Regelset B (genaamd HRSs, gebaseerd op het werk van Nipkow). Omdat de regels zo verschillend waren, konden de chefs niet echt eerlijk tegen elkaar strijden. Het was also kind met het vergelijken van een chef die alleen een garde gebruikt met een chef die alleen een blender gebruikt; ze maken allebei eten, maar de mechanica zijn te verschillend om te beoordelen wie sneller of beter is.

Het Probleem: Twee Verschillende Talen

In de wereld van de computerwetenschappen zijn deze "recepten" wiskundige regels voor het herschrijven van symbolen.

Regelset A (AFSs) is als een strikte keuken waar je ingrediënten alleen kunt verwisselen als ze exact overeenkomen. Als een recept zegt "voeg bloem toe", kun je niet "bloem gemengd met melk" toevoegen, tenzij je dat expliciet opschrijft.
Regelset B (HRSs) is flexibeler. Het staat "beta-reductie" toe, wat is als het automatisch vereenvoudigen van een complexe instructie. Als een recept zegt "neem het resultaat van het mengen van X en Y", laten HRSs je het mengen direct uitvoeren en het resultaat gebruiken, terwijl Regelset A je misschien moet laten wachten tot het allerlaatste moment.

De auteurs van dit artikel, Johannes Niederhauser en Aart Middeldorp, wilden een eerlijk speelveld creëren waar chefs die Regelset B gebruiken, in dezelfde arena kunnen strijden als chefs die Regelset A gebruiken.

De Oplossing: Een Nieuwe "Universele Vertaler"

Het artikel introduceert een nieuwe, zorgvuldig gedefinieerde subset van recepten genaamd Extended Pattern Rewrite Systems (EPRSs). Denk aan dit als een speciale "Universele Vertaler"-indeling.

De auteurs zeiden niet simpelweg: "Laten we iedereen gewoon HRSs laten gebruiken." In plaats daarvan vonden ze een specifieke, eenvoudige manier om deze flexibele HRS-recepten te schrijven, zodat ze begrepen konden worden door het bestaande wedstrijdsysteem (dat een formaat genaamd STMRS gebruikt).

Ze ontdekten een "sweet spot" van recepten waarbij:

De Regels zijn Strikt maar Slim: Ze definieerden een klasse van recepten waarbij de "linkerzijde" (het deel van het recept dat wordt gematcht) een specifiek patroon volgt dat een "Extended Pattern" wordt genoemd. Dit zorgt ervoor dat wanneer je ingrediënten probeert te matchen, de computer niet in de war raakt of vastloopt.
De Vertaling Werkt Perfect: Ze bewezen wiskundig dat als je een recept neemt dat geschreven is in dit nieuwe "Universele Vertaler"-formaat (EPRS) en dit door het bestaande wedstrijdsysteem (STMRS) laat lopen, het resultaat exact hetzelfde is als wanneer je het met de originele, complexere HRS-regels zou draaien.

De "Magische Truc" Analogie

Stel je een complexe magische truc voor (de HRS-regel) die inhoudt dat er een konijn uit een hoed verschijnt.

De Oude Manier: Om te bewijzen dat de truc werkt, moest je een hele nieuwe stage bouwen die specifiek voor die specifieke konijn was.
De Nieuwe Manier: De auteurs lieten zien dat als je de konijn, de hoed en de toverstaf op een zeer specifieke, eenvoudige manier arrangeert (de "goed gedrag vertonende" EPRS), je exact dezelfde magische truc kunt uitvoeren op het standaard podium dat al gebouwd is voor de wedstrijd (de STMRS).

Ze bewezen dat elke keer dat de HRS-chef een stap doet, de STMRS-chef een stap gevolgd door een snelle "opruiming" (genaamd $\beta$ -normalisatie) kan doen en met exact hetzelfde resultaat eindigt.

Waarom Dit Belangrijk Is

Dit gaat niet alleen over wiskunde; het gaat over eerlijkheid en vooruitgang.

Meer Chefs, Meer Competitie: Door deze specifieke subset te definiëren, kunnen de wedstrijdorganisatoren nu meer tools (chefs) uitnodigen die de HRS-stijl gebruiken om mee te strijden.
Betere Benchmarks: Het stelt de wedstrijddatabase (TPDB) in staat om een breder scala aan problemen op te nemen zonder de regels van het spel te breken.
Bewezen Equivalentie: Het artikel gokt niet alleen dat dit werkt; het biedt een rigoureus wiskundig bewijs (Stelling 15) dat de twee methoden equivalent zijn voor deze specifieke klasse van problemen.

De Kern van de Zaak

De auteurs hebben succesvol een brug geslagen tussen twee verschillende manieren van denken over computer-rewriting. Ze hebben aangetoond dat door de regels een klein beetje in te perken (door gebruik te maken van "goed gedrag vertonende" patronen), de flexibele HRS-stijl perfect kan werken binnen het bestaande TermCOMP-raamwerk. Dit legt de formele grondslag voor een nieuwe, eerlijke subcategorie in de wedstrijd waar krachtigere tools eindelijk tegen elkaar kunnen strijden.

Noot: Het artikel richt zich volledig op de wiskundige basis van deze equivalentie. Het bespreekt geen specifieke praktische toepassingen zoals medische diagnose of klinisch gebruik, noch voorspelt het toekomstige technologieën buiten de reikwijdte van de wedstrijd zelf. Het is puur gericht op het maken van de "kookwedstrijd" voor computerbewijzen inclusiever en rigoureuzer.

Technische Samenvatting: Naar een HRS-categorie in TermCOMP

Probleemstelling
De jaarlijkse Termination Competition (TermCOMP) bevat een categorie voor hogere-orde herschrijfsystemen. Historisch gezien heeft deze categorie gebruikgemaakt van de semantiek van Algebraïsche Functionele Systemen (AFS'en), die steunen op gewone matching en expliciete $\beta$ -reductieregels. Hoewel Nipkows Higher-Order Rewrite Systems (HRS'en), die herschrijven modulo $\beta\eta$ en doorgaans Miller's patterns (PRSs) of de recentere Deterministic Higher-Order Pattern Rewrite Systems (DPRSs) gebruiken, goed gevestigde formalismen zijn, zijn ze niet volledig geïntegreerd in het bestaande TermCOMP-framework. De uitdaging ligt in het verzoenen van de semantiek van HRS'en (herschrijven modulo $\beta\eta$ ) met het bestaande TermCOMP-framework (gebaseerd op AFS'en en meta-substituties) om tools die gericht zijn op HRS'en direct te laten concurreren met tools die gericht zijn op AFS'en.

Methodologie
De auteurs stellen een formele brug voor tussen HRS'en en de huidige TermCOMP hogere-orde semantiek, gedefinieerd als Simply-Typed Meta-Substitution Rewrite Systems (STMRSs). De methodologie omvat drie hoofdstappen:

Generalisatie van patronen: De auteurs introduceren Extended Pattern Rewrite Systems (EPRSs), een subclassie van HRS'en die zowel PRSs als DPRSs generaliseert. EPRSs maken gebruik van "Extended Patterns" (EPATs), die de deterministische matching-beperkingen van DPRSs versoepelen, terwijl ze een structuur behouden waarbij vrije variabelen worden toegepast op niet-abstractie argumenten. Deze klasse is primair gedefinieerd om de theoretische bewijsvoering te faciliteren, eerder dan als een op zichzelf staand praktisch instrument.
Extensie van STMRS-semantiek: De auteurs breiden de definitie van STMRS-regels (de huidige TermCOMP-standaard) uit om toe te staan dat de linkerzijden EPATs zijn in plaats van alleen standaard patronen. Ze introduceren het concept van well-behaved (goed gedrag vertonende) en quasi-well-behaved termen. Deze syntactische beperkingen zorgen ervoor dat wanneer meta-substituties worden toegepast, de resulterende termen in $\beta$ -normaalvorm blijven (specifiek $\beta\eta$ -lange normaalvorm) zonder nieuwe $\beta$ -redexen te genereren die extra reductiestappen zouden vereisen.
Implementatie via genormaliseerd herschrijven: De kern van de technische bijdrage is het vaststellen dat herschrijven in een well-behaved STMRS, gevolgd door $\beta$ -normalisatie, herschrijven in de overeenkomstige EPRS simuleert. De auteurs definiëren een vertaling tussen gewone substituties (gebruikt in EPRSs) en meta-substituties (gebruikt in STMRSs) om te bewijzen dat deze twee systemen gelijk zijn met betrekking tot terminatie.

Belangrijkste Bijdragen

Definitie van EPRSs: Een nieuwe syntactische subclassie van HRS'en die DPRSs generaliseert, waardoor een breder scala aan benchmarks mogelijk wordt gemaakt terwijl beheersbare matching-eigenschappen behouden blijven.
Syntactische Beperkingen voor Equivalentie: De introductie van "well-behaved" STMRS-regels. Deze regels beperken de linkerzijden tot well-behaved en de rechterzijden tot quasi-well-behaved. Dit zorgt ervoor dat de toepassing van meta-substituties geen $\beta$ -redexen creëert, waardoor de $\beta$ -normaalvorm van termen behouden blijft.
Formeel Equivalentie-theorema: Het artikel bewijst dat voor een well-behaved STMRS $R$ en een term $s$ in $\beta\eta$ -lange normaalvorm, een herschrijfstap in de EPRS-semantiek ( $s \to_R t$ ) plaatsvindt dan en slechts dan als een herschrijfstap in de STMRS-semantiek gevolgd door $\beta$ -normalisatie plaatsvindt ( $s \Rightarrow_R \cdot \Rightarrow!_\beta t$ ).

Resultaten
Het primaire resultaat is Theorem 15, die de correspondentie vaststelt tussen de herschrijfrelaties van well-behaved STMRSs en hun overeenkomstige EPRSs. Specifiek:

$s \Rightarrow_R \cdot \Rightarrow!_\beta t$ dan en slechts dan als $s \to_R t$ (waarbij $R$ als een EPRS wordt beschouwd).
Dit leidt tot Corollary 20, die stelt dat de terminatie van de strategie "herschrijf dan $\beta$ -normaliseer" in een well-behaved STMRS samenvalt met de universele terminatie van de overeenkomstige EPRS.

De auteurs demonstreren dat deze equivalentie standhoudt voor termen in $\beta\eta$ -lange normaalvorm. Zij merken op dat voor tweede-orde STMRSs de correspondentie nog sterker is, aangezien meta-substituties in die specifieke context geen $\beta$ -redexen kunnen creëren, wat leidt tot een één-op-één mapping tussen stappen.

Betekenis
Het artikel beweert de formele basis te leggen voor een HRS (sub)categorie in TermCOMP. Door een syntactisch controleerbare deelverzameling van benchmarks (well-behaved STMRSs) te definiëren binnen het bestaande TPDB-formaat, stellen de auteurs het volgende mogelijk:

Directe Competitie: Tools ontworpen voor HRS'en (gebruikmakend van $\beta\eta$ -herschrijven) kunnen nu direct concurreren met tools ontworpen voor AFS'en binnen dezelfde categorie, aangezien hun terminatie-eigenschappen onder de voorgestelde semantiek bewezen samenvallen.
Breder Tool-ondersteuning: Het implementatieresultaat maakt het mogelijk om eigenschappen verder te gaan dan enkel terminatie, aangezien de simulatie gebaseerd is op een stap-voor-stap correspondentie in plaats van enkel een globale terminatie-eigenschap.
Verfijning van Bestaand Werk: Het resultaat versterkt eerdere implementaties van PRSs in AFSM'en (Kop) en combinatorische systemen (van Oostrom en van Raamsdonk) door ze uit te breiden naar een algemenere klasse van HRS'en (EPRSs) en een rigoureus bewijs te leveren voor de equivalentie van genormaliseerd herschrijven en hogere-orde herschrijven.

De auteurs blijven bescheiden over de reikwijdte en erkennen dat het resultaat niet alle HRS'en dekt, omdat meta-substitutie strikt minder krachtig is dan volledige hogere-orde substitutie. Zij beargumenteren echter dat de gedefinieerde subclassie voldoende is om een aanzienlijk deel van de bestaande benchmarks en de specifieke DPRSs die in hun eerdere werk zijn geïntroduceerd, te accommoderen.