💻 computer science

Labelled Process Logic

Dit artikel introduceert een uniform cyclisch gelabeld bewijstheoretisch kader, bestaande uit de systemen G3PPL en G3FOPL, dat een volledige behandeling van zowel propositionele als eerste-orde proceslogica bereikt door formules te verrijken met labels om traceer- en update-informatie tijdens afleidingen expliciet bij te houden.

Oorspronkelijke auteurs: Yuanrui Zhang

Gepubliceerd 2026-06-10

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yuanrui Zhang

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 probeert te bewijzen dat een robot nooit zal crashen tijdens het navigeren door een doolhof.

In de oude manier van doen (genaamd "Dynamische Logica") controleerde je alleen de eindbestemming van de robot. Je vroeg: "Als de robot hier begint en deze instructies volgt, komt hij dan terecht in de veilige zone?" Dit is als het controleren van een kaart alleen bij de finishlijn. Het vertelt je of je bent aangekomen, maar niet of je onderweg van een klif bent gereden.

Process Logic is een upgrade. Het geeft om de volledige reis. Het vraagt: "Is de robot op de weg gebleven, heeft hij de kliffen vermeden en heeft hij bij elke stap van de rit de regels gevolod?" Dit is veel moeilijker te bewijzen omdat je de volledige geschiedenis van de robot moet volgen, niet alleen zijn laatste stop.

Het artikel van Yuanrui Zhang introduceert een nieuw, krachtig hulpmiddel genaamd Labelled Process Logic om dit moeilijke wiskundige probleem op te lossen. Zo werkt het, met behulp van eenvoudige analogieën:

1. Het Probleem: De "Splitsing"-nachtmerrie

Stel je voor dat je probeert te bewijzen dat een robot veilig door een lange tunnel kan rijden die bestaat uit twee secties: Sectie A en Sectie B.

In traditionele wiskundige bewijzen, om te bewijzen dat de hele reis veilig is, moet je het probleem vaak "splitsen". Je probeert te bewijzen dat Sectie A veilig is, dan te bewijzen dat Sectie B veilig is, en probeert vervolgens de twee bewijzen aan elkaar te lijmen.
Het probleem is dat de "lijm" rommelig is. Als het pad van de robot in Sectie A de manier waarop Sectie B zich gedraagt verandert, wordt de wiskunde ongelooflijk complex. Bestaande hulpmiddelen konden eenvoudige tunnels aan, maar liepen vast wanneer de tunnels complex werden, zichzelf in lussen terugvoerden, of veel verschillende mogelijke paden hadden.

2. De Oplossing: De "Rugzak" (Labels)

Het grote idee van de auteur is om te stoppen met het proberen aan elkaar lijmen van de stukken aan het einde. Geef het bewijs in plaats daarvan een rugzak (een "Label").

Hoe het werkt: Terwijl het bewijs door de instructies van de robot beweegt, noteert het niet alleen "Is dit veilig?", maar het schrijft ook op: "We zijn bij stap 5, de robot is naar links gedraaid en de batterij staat op 80%."
De Magie: Deze "rugzak" (het label) draagt de geschiedenis van de reis binnenin het bewijs zelf.
- In plaats van het probleem te splitsen in twee moeilijke stukken, voegt het bewijs simpelweg de nieuwe stap toe aan de rugzak.
- Als de robot Stap A doet en dan Stap B, dan werkt het bewijs de rugzak simpelweg bij naar Geschiedenis: Stap A + Stap B.
- Dit maakt de wiskunde veel schoner. Je hebt geen complexe regels nodig om dingen aan elkaar te "lijmen"; je blijft gewoon de lijst bijwerken van wat er is gebeurd.

3. Het Loop-probleem: De "Oneindige Gang"

Computers en robots hebben vaak lussen (bijv. "Blijf rijden totdat je een rood licht ziet").

Als je een lus probeert te bewijzen met standaard wiskunde, kun je vast komen te zitten in een oneindige gang. Je bewijst stap 1, dan stap 2, dan stap 3... en omdat de lus zich herhaalt, bereik je het einde van het bewijs nooit.
De Cyclische Fix: De auteur staat toe dat het bewijs "op zichzelf terugkeert". Stel je een bewijs voor dat lijkt op een slang die zijn eigen staart opeet.
- Het bewijs zegt: "Ik ben bij stap 10. Ik weet dat ik eerst bij stap 1 was. Omdat de regels hetzelfde zijn, kan ik terugspringen naar stap 1 en zeggen: 'Ik heb dit deel al gecontroleerd, dus het zit goed.'"
- De Veiligheidscontrole: Om te zorgen dat dit niet valsspelen is, voegt de auteur een regel toe: Elke keer dat het bewijs terugkeert in een lus, moet het bewijzen dat de "rugzak" (het label) op een specifieke, krimpende manier is veranderd. Het is als een spel waarbij je alleen mag terugkeren in de loop als je nog minder koekjes in je pot hebt. Uiteindelijk raak je de koekjes op, wat bewijst dat de loop veilig en eindig is.

4. Twee Versies van het Hulpmiddel

De auteur bouwt twee versies van dit systeem:

G3PPL (De Eenvoudige Versie): Werkt voor abstracte logische puzzels waarbij je alleen geeft om "Waar" of "Onwaar" staten. Het gebruikt labels om eenvoudige paden te volgen.
G3FOPL (De Geavanceerde Versie): Werkt voor echte wiskunde met getallen en variabelen (zoals x = x + 1). Hier houdt de "rugzak" niet alleen het pad bij, maar houdt het ook updates bij. Als de robot een getal verandert, legt het label die verandering expliciet vast (bijv. "x is nu 5"). Dit stelt het systeem in staat om echte computerprogramma's met wiskunde erin te verwerken.

De Kernboodschap

De auteur beweert het eerste complete, betrouwbare wiskundige kader te hebben gebouwd dat eigenschappen kan bewijzen over de volledige executiepaden van complexe computerprogramma's, inclusief lussen en lussen met wiskunde.

Vóór: We konden alleen gemakkelijk bewijzen waar een programma eindigt, of zeer eenvoudige paden afhandelen.
Nu: We hebben een verenigd systeem (met behulp van "rugzakken" en "veilige lussen") dat complexe, stap-voor-stap gedragingen kan bewijzen voor zowel eenvoudige logica als complexe wiskundige programma's.

De auteur bewijst dat dit systeem Sound (het liegt nooit; als het zegt dat een programma veilig is, dan is het dat ook echt) en Complete (het kan alles bewijzen wat daadwerkelijk waar is) is. Dit is een belangrijke stap voorwaarts in het garanderen dat software zich precies gedraagt zoals we verwachten, van de eerste seconde tot de laatste.

Technische Samenvatting: Gelabelde Proceslogica

1. Probleemstelling

Proceslogica (PL) breidt Dynamische Logica (DL) uit door de focus te verschuiven van het redeneren over eindtoestanden van programma's naar het redeneren over volledige executietrajecten. Hoewel de propositionele theorie van Proceslogica (PPL) goed begrepen is wat betreft beslisbaarheid en volledigheid, presenteert de eerste-orde uitbreiding (FOPL) aanzienlijke uitdagingen.

De kern van de moeilijkheid ligt in het compositionele redeneren dat vereist is voor eerste-orde proceslogica over reguliere programma's. In standaard Dynamische Logica stelt een formule $[\alpha]\phi$ dat elke terminerende executie van $\alpha$ eindigt in een toestand die $\phi$ bevredigt. In Proceslogica stelt $[\alpha]\pi$ dat elk executietraject van $\alpha$ een temporele eigenschap $\pi$ (uitgedrukt via Lineaire Temporele Logica-operatoren zoals next, always, eventually en until) bevredigt.

Bestaande compositionele calculi voor fragmenten van deze logica (bijv. Beckert's sequentencalculus voor deterministische while-programma's, of uitbreidingen zoals DLT en DTL) slagen er niet in een volledige behandeling te bieden voor de volledige eerste-orde proceslogica over reguliere (potentieel niet-deterministische) programma's. Specifiek:

Compositionele regels voor sequentiële programma's (het splitsen van een trajecteigenschap $\pi$ over $\alpha; \beta$ ) zijn vaak sterk afhankelijk van de specifieke vorm van de temporele formule (bijv. specifieke regels voor "always" versus "eventually").
Sommige voorgestelde regels zijn onvoldoende voor algemene reguliere programma's omdat tests in sequentiële composities trajecten kunnen blokkeren, wat eenvoudige compositionele splitsingen ongeldig maakt.
Geen enkel bestaand systeem biedt een uniform kader waarin trajectgebaseerde eigenschappen en eerste-orde berekeningen binnen dezelfde bewijsstructuur worden afgehandeld.

2. Methodologie: Cyclische Gelabelde Bewijssystemen

Het artikel stelt een nieuw bewijs-theoretisch kader voor dat formules van proceslogica verrijkt met labels om executie-informatie expliciet vast te leggen tijdens afleidingen, in plaats van te vertrouwen op steeds complexere compositionele regels.

2.1 Gelabelde Formules

De auteurs introduceren gelabelde formules van de vorm $\sigma : \phi$ , waarbij:

$\phi$ een proceslogica-formule is.
$\sigma$ $σ$ een label is dat het tot nu toe geaccumuleerde executietraject of programmaconfiguratie vertegenwoordigt.
- In Propositionele Proceslogica (PPL) zijn labels trajecten van werelden ( $\sigma \in L$ ), geconstrueerd uit wereldvariabelen, trajectvariabelen en concatenatie.
- In Eerste-Orde Proceslogica (FOPL) zijn labels verrijkt met programma-updates ( $U$ ) om het cumulatieve effect van toewijzingen (bijv. $\{u := e\}$ ) over een rekenkundige structuur vast te leggen.

Deze aanpak maakt tussenliggende executie-informatie beschikbaar binnen het bewijssysteem. Bij consequent kan het bewijssysteem niet langer sequentiële trajecten splitsen met speciale temporele regels op het punt van de sequentie; in plaats daarvan ontvouwt het de programmastructuur terwijl informatie in het label wordt geaccumuleerd.

2.2 Cyclische Bewijsstructuur

Omdat reguliere programma's iteratie ( $\alpha^*$ ) bevatten, kan de zoektocht naar bewijzen oneindige afleidingen genereren. Om dit te behandelen, hanteren de auteurs cyclische bewijstheorie.

Prebewijzen: Eindige bomen waarbij de bladknopen ("buds") terug kunnen linken naar een voorouderknoop met identieke syntactische vorm (modulo variabele-hernoeming).
Cyclische Conditie: Om de correctheid te waarborgen, zijn niet alle cycli geldig. Het paper definieert een progressieve afleidingsreeks. Een afleiding is een geldige cyclische bewijs als elke oneindige pad een "progressieve stap" bevat (bijv. het toepassen van een regel die de complexiteit van het traject of de formule vermindert).
Correctheidsmechanisme: De auteurs bewijzen de correctheid door aan te tonen dat elke oneindige afleidingspad die voldoet aan de cyclische conditie een oneindige daling induceert in een welgeordende multiset-ordening van "minimale tegenvoorbeelden-trajecten". Deze contradictie zorgt ervoor dat geen enkele ongeldige formule bewezen kan worden.

2.3 De Bewijssystemen

Twee specifieke systemen worden gedefinieerd:

G3PPL: Een cyclisch gelabeld bewijssysteem voor Propositionele Proceslogica. Het breidt gelabelde sequentietechnieken voor modale logica uit en past deze aan voor trajectsemantiek.
G3FOPL: Een cyclisch geland bewijssysteem voor Eerste-Orde Proceslogica. Het breidt G3PPL uit door atomaire programmaregels te vervangen door regels voor toewijzingen (het bijwerken van het label) en door standaard eerste-orde kwantificatieregels toe te voegen.

3. Belangrijkste Bijdragen

Het artikel levert de volgende specifieke bijdragen:

Gelabelde Formules: De introductie van trajectlabels voor PPL en update-gebaseerde labels voor FOPL, waardoor de executiegeschiedenis expliciet binnen de bewijsstructuur kan worden gevolgd.
Cyclische Gelabelde Systemen: De definitie van G3PPL en G3FOPL, die een gemeenschappelijk gelabeld kader delen maar specifieke regels gebruiken voor respectievelijk propositionele en eerste-orde proceslogica.
Correctheidsbewijzen: Een bewijs van de correctheid voor beide systemen. Het argument berust op het reduceren van elke progressieve oneindige afleidingspad tot een oneindige daling in een welgeordende multiset-ordening van minimale tegenvoorbeelden-trajecten.
Volledigheidsbewijzen:
- Voor G3PPL wordt de volledigheid vastgesteld door aan te tonen dat het gelabelde systeem elke axioma en regel van het gevestigde Hilbert-stijl bewijssysteem voor PPL kan afleiden.
- Voor G3FOPL wordt de volledigheid vastgesteld door het klassieke volledigheidsargument voor Eerste-Orde Dynamische Logica (FODL) aan te passen aan de trajectgebaseerde setting, gebruikmakend van rekenkundige coderingen.

4. Resultaten

Uniform Kader: Het artikel slaagt erin een uniform kader te construëren waarin trajectgebaseerde programmeigenschappen en eerste-orde berekeningen binnen dezelfde bewijsstructuur worden afgehandeld.
Volledigheid voor Reguliere Programma's: De systemen bieden het eerste volledige logische kader voor volledige eerste-orde proceslogica over reguliere programma's (inclusclusief niet-deterministische keuze en iteratie).
Correctheid en Volledigheid: Zowel G3PPL als G3FOPL zijn bewezen correct en volledig met betrekking tot hun respectievelijke semantiek.

5. Betekenis

Het artikel stelt dat dit werk een langdurig gat in de literatuur dicht. Eerdere systemen waren ofwel:

Beperkt tot deterministische programma's (bijv. DLT, DTL).
Niet volledig voor algemene reguliere programma's.
Niet in staat om alle LTL-operatoren (bijv. until) uniform te behandelen in aanwezigheid van niet-determinisme.

Door labels te gebruiken om executie-informatie te externaliseren en cyclische bewijzen om iteratie te behandelen, bieden de auteurs een geprincieerd en uniform mechanisme voor het redeneren over trajecteigenschappen. Dit maakt de verificatie van specificaties mogelijk waarbij tussenliggend gedrag essentieel is, zonder dat er ad-hoc compositionele regels nodig zijn voor elke temporele operator. Het kader verenigt de behandeling van propositionele en eerste-orde niveaus en biedt een robuuste basis voor programmaverificatie waarbij complexe temporele eigenschappen betrokken zijn.