💻 computer science

Taking Complete Finite Prefixes To High Level, Symbolically

Deze paper introduceert en evalueert een algoritme voor het construeren van complete eindige prefixen van symbolische ontvouwingen van high-level Petri-netten, waarmee bestaande verificatiemethoden worden uitgebreid naar netten met oneindig veel bereikbare markeringen.

Oorspronkelijke auteurs: Nick Würdemann, Thomas Chatain, Stefan Haar, Lukas Panneke

Gepubliceerd 2026-04-08

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Nick Würdemann, Thomas Chatain, Stefan Haar, Lukas Panneke

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

De Kunst van het Voorspellen: Hoe Computers Complexe Spelletjes Sneller Oplossen

Stel je voor dat je een enorm ingewikkeld bordspel speelt, zoals een uitgebreide versie van Mastermind of een puzzel met emmers water. Je wilt weten: "Is het mogelijk om deze specifieke eindstand te bereiken?" of "Kan ik deze situatie voorkomen?"

In de wereld van computers en software worden zulke systemen vaak gemodelleerd met Petri-netten. Denk hierbij aan een soort blauwdruk van een fabriek, een verkeerssysteem of een computerprogramma. De netten bestaan uit "plekken" (waar dingen kunnen staan) en "overgangen" (acties die dingen verplaatsen).

Het probleem? Als je systeem groeit, wordt het aantal mogelijke situaties (de "markeringen") gigantisch. Het is alsof je probeert alle mogelijke zetten in een schaakpartij te berekenen, maar dan met miljarden borden tegelijk. Dit heet de "state explosion" (explosie van toestanden).

De auteurs van dit paper, Nick, Thomas, Stefan en Lukas, hebben een slimme oplossing bedacht om dit probleem op te lossen, zelfs voor systemen die op het eerste gezicht onbegrensd lijken.

1. De Traditionele Aanpak: De Ontvouwde Lijst

Stel je voor dat je een Petri-net wilt analyseren. De oude manier is om het systeem "uit te vouwen".

De Metafoor: Stel je een boom voor. De stam is de start. Elke tak is een mogelijke actie. Als je een actie doet, krijg je nieuwe takken.
Het Probleem: Bij een simpel systeem met veel kleuren (bijvoorbeeld 100 verschillende soorten tokens) moet je voor elke kleur een aparte tak in de boom tekenen. Als je 100 kleuren hebt en 10 stappen, krijg je $100^{10}$ takken. Dat is een boom die zo groot is als het universum. Computers gaan hierbij vastlopen.

2. De Nieuwe Aanpak: De Symbolische Unfoldings

De auteurs introduceren een manier om deze boom symbolisch te tekenen.

De Metafoor: In plaats van elke tak apart te tekenen, teken je één tak en schrijf je erbij: "Deze tak geldt voor alle kleuren tussen 1 en 100."
Hoe werkt het? Ze gebruiken wiskundige regels (guards) om te zeggen: "Als de variabele $x$ groter is dan 0, dan gebeurt dit." In plaats van 100 takken te maken, maken ze er één, met een label dat zegt: "Dit geldt voor elke $x > 0$ ."

Dit is de kern van hun werk: ze hebben een algoritme (een recept voor de computer) ontwikkeld dat deze symbolische boom kan bouwen, maar dan wel op een slimme manier. Ze stoppen op het juiste moment, zodat de boom niet oneindig groot wordt, maar toch alle informatie bevat die je nodig hebt om te weten of iets mogelijk is.

3. De "Stop-Stop" Regels (Cut-off Events)

Een groot deel van het papier gaat over het bepalen van het juiste moment om te stoppen met het tekenen van takken.

Het idee: Als je een tak hebt getekend die precies dezelfde situatie oplevert als een tak die je al eerder hebt getekend, waarom zou je dan doorgaan? Je hebt die situatie al "gezien".
De uitdaging: Bij symbolische netten is dit lastiger. Je ziet niet één situatie, maar een hele verzameling. De auteurs hebben een nieuwe regel bedacht: "Als de verzameling van alle mogelijke situaties die je nu ziet, al volledig is gedekt door wat je eerder hebt gezien, dan stop je."
De slimme truc: Ze gebruiken wiskundige logica (SMT-solvers) om te checken of die verzamelingen inderdaad hetzelfde zijn, zonder ze één voor één op te sommen. Het is alsof je zegt: "Ik heb een doos met alle rode ballen al gezien, dus ik hoef niet te kijken of de nieuwe doos ook rode ballen heeft."

4. De "Symbolisch Compacte" Netten

Er is een speciale categorie netten die oneindig veel situaties kunnen hebben (bijvoorbeeld een systeem dat elke natuurlijke getal kan genereren). Voor deze netten werkt de oude methode helemaal niet.

De oplossing: De auteurs hebben een nieuwe klasse van netten bedacht, genaamd "symbolisch compact".
De Metafoor: Stel je een trap voor die oneindig hoog is. Je kunt niet elke tree aflopen. Maar als je weet dat je altijd binnen 10 stappen een bepaalde verdieping kunt bereiken, dan hoef je niet de hele trap te bekijken. Je kijkt alleen naar de eerste 10 treden.
Ze hebben hun algoritme aangepast zodat het werkt voor deze oneindige systemen, zolang ze maar "beperkt diep" zijn in hun logica.

5. De Test: Vier Nieuwe Puzzels

Om hun theorie te bewijzen, hebben ze een prototype gebouwd (een softwaretool genaamd COLORUNFOLDER) en deze getest op vier soorten puzzels:

Vork en Samenvoeging (Fork & Join): Een systeem dat veel dingen tegelijk doet. Hier was de nieuwe methode ontzettend snel (seconden) terwijl de oude methode vastliep (uren of nooit).
Waterpuzzel: Een klassieke puzzel met emmers. Hier was de nieuwe methode soms iets trager, omdat de oude methode hier net zo goed werkte.
Hobbits en Orks: Een rivieroversteekpuzzel. De nieuwe methode deed het goed, vooral bij grote aantallen.
Mastermind: Het raadselspel. Hier was de nieuwe methode de absolute winnaar. Terwijl de oude methode vastliep bij grotere codes, deed de nieuwe methode het in een flits.

Conclusie: Waarom is dit belangrijk?

De auteurs hebben een brug geslagen tussen twee werelden: de compacte, abstracte manier van kijken naar systemen (hoog niveau) en de gedetailleerde, precieze manier (laag niveau).

Voor de leek: Het is alsof ze een manier hebben gevonden om een gigantische stad te plotten op één vel papier, zonder dat je de details van elke straat mist.
Het resultaat: Softwareontwikkelaars en veiligheidsanalisten kunnen nu veel complexere systemen controleren op fouten of beveiligingslekken, die voorheen te groot waren om te analyseren. Ze kunnen nu zeggen: "Ja, dit systeem is veilig," of "Nee, hier zit een gat in," zelfs als het systeem oneindig veel variaties heeft.

Kortom: Ze hebben de computer leren "schematisch" te denken in plaats van "letterlijk", waardoor hij veel sneller en slimmer kan werken.

Titel: Taking Complete Finite Prefixes To High Level, Symbolically

Auteurs: Nick Würdemann, Thomas Chatain, Stefan Haar, Lukas Panneke
Publicatie: Fundamenta Informaticae 192(3-4) (2024)

1. Probleemstelling

Petri-netten zijn een gevestigde formalisme voor het modelleren van gedistribueerde systemen. Er bestaat een fundamenteel spanningsveld tussen twee benaderingen:

Laag niveau (P/T Petri-netten): Deze bieden een gedetailleerde weergave van het systeemgedrag, maar kunnen bij complexe systemen leiden tot een "toestandexplosie" (state explosion problem), waarbij het aantal bereikbare markeringen exponentieel groeit.
Hoog niveau (High-level/Colored Petri-netten): Deze zijn een beknopte representatie waarbij plaatsen tokens met verschillende "kleuren" (waarden) kunnen dragen. Hoewel ze compacter zijn, vertegenwoordigen ze vaak een onderliggend P/T-net met een oneindig aantal markeringen of een extreem groot aantal.

Bestaande methoden voor verificatie, zoals het gebruik van complete finite prefixes van unfoldings (ontvouwingen) voor P/T-netten (gebaseerd op het werk van Esparza, Römer en Vogler, de "ERV-algoritme"), zijn niet direct toepasbaar op hoog-niveau netten. Bestaande symbolische unfoldings voor hoog-niveau netten zijn vaak oneindig, en er bestaat geen garantie voor een eindige, complete prefix die alle bereikbare markeringen dekt, vooral niet bij netten met oneindig veel bereikbare markeringen.

De kernvraag is: Hoe kunnen we de efficiënte methode van complete finite prefixes toepassen op de symbolische unfoldings van hoog-niveau Petri-netten, zonder eerst het onderliggende P/T-net te expanderen (wat vaak onmogelijk of inefficiënt is)?

2. Methodologie

De auteurs combineren concepten uit de theorie van P/T-netten (complete prefixes, adequate orders) met de theorie van symbolische unfoldings voor hoog-niveau netten.

A. Definitie van een Compleet Eindige Prefix op Symbolisch Niveau

De auteurs definiëren wat een "complete finite prefix" betekent voor een symbolische unfolding. Een prefix is compleet als hij alle bereikbare markeringen van het net dekt en alle mogelijke overgangen vanuit die markeringen toelaat.

B. De Klasse NF (Netten met Eindige Bereikbare Markeringen)

Eerst wordt een klasse van netten, genaamd NF, gedefinieerd waarvoor het algoritme werkt:

Het net is veilig (safe): elke plaats heeft maximaal één token.
De guards (voorwaarden) zijn uitgedrukt in een beslisbare theorie (bijv. Presburger-aritmetiek).
Er zijn eindig veel bereikbare markeringen.

Voor deze klasse wordt een gegeneraliseerd ERV-algoritme (Alg. 1) ontwikkeld. Dit algoritme bouwt een prefix op door gebeurtenissen (events) toe te voegen totdat een "cut-off" criterium wordt bereikt.

C. Generalisatie van Adequate Orders en Cut-off Criteria

In laag-niveau netten wordt een cut-off bepaald wanneer een nieuwe gebeurtenis leidt tot een markering die al eerder is gezien. Bij hoog-niveau netten is dit complexer omdat één gebeurtenis een verzameling van markeringen kan vertegenwoordigen.

Adequate Order: Een partiële orde op configuraties die zorgt dat kleinere configuraties eerst worden verwerkt.
Cut-off Criterium: Een gebeurtenis $e$ is een cut-off als de verzameling van markeringen die door de kegel-configuratie $[e]$ wordt gegenereerd, een deelverzameling is van de vereniging van markeringen van alle eerdere configuraties $C$ met $C \prec [e]$ . Dit voorkomt dat het algoritme oneindig doorgaat bij herhalende patronen.

D. Omgaan met Oneindig Veel Markeringen (Klasse NSC)

Voor netten met oneindig veel bereikbare markeringen (maar waar elke markering binnen een vast aantal stappen bereikbaar is, de klasse NSC - Symbolically Compact), faalt het standaard algoritme.

De auteurs passen het cut-off criterium aan naar cut-off*. In plaats van alleen te kijken naar kegel-configuraties, wordt gecontroleerd of de markeringen van een nieuwe gebeurtenis al zijn gezien in elke kleinere configuratie.
Om dit te controleren zonder de volledige toestandruimte op te slaan, gebruiken ze symbolische representaties (constraints) van de markeringen. De inclusie van markeringsverzamelingen wordt omgezet in een logische implicatie tussen constraints, wat met een SMT-solver (CVC5) in eindige tijd kan worden gecontroleerd.

3. Belangrijkste Bijdragen

Unificatie van Concepten: De auteurs verenigen de theorie van complete finite prefixes (voor P/T-netten) en symbolische unfoldings (voor hoog-niveau netten) tot een coherent raamwerk.
Generalisatie van het ERV-algoritme: Ze presenteren een algoritme dat complete finite prefixes construeert voor een brede klasse van veilige hoog-niveau netten. Dit algoritme is een directe generalisatie van het bekende ERV-algoritme; als een P/T-net als hoog-niveau net wordt gezien, vallen de resultaten exact samen.
Uitbreiding naar Oneindige Markeringen: Ze identificeren de klasse van symbolically compact netten en ontwikkelen een aangepast algoritme met een cut-off*-criterium en symbolische constraint-checking om ook voor deze netten een eindige prefix te garanderen.
Concept van "Mode-Determinism": Ze introduceren een nieuwe net-eigenschap: mode-determinism. Een net is mode-deterministisch als er in elke bereikbare markering voor elke transitie maximaal één geldige vuurmaat (mode) bestaat. Dit blijkt een sterke indicator te zijn voor de prestatieverschillen tussen symbolische en laag-niveau benaderingen.
Implementatie en Validatie: Een prototype implementatie genaamd COLORUNFOLDER (in Java) is ontwikkeld en getest op vier nieuwe benchmark-families.

4. Resultaten en Experimenten

De auteurs testen hun implementatie op vier benchmark-families:

Fork And Join: Een net met hoge "mode-nondeterminism".
- Resultaat: De symbolische aanpak is extreem snel en onafhankelijk van het aantal kleuren. De laag-niveau aanpak faalt of is exponentieel traag door de enorme toestandruimte.
Water Pouring Puzzle: Een logische puzzel die mode-deterministisch is.
- Resultaat: Omdat er weinig keuzevrijheid is in vuurmodi, zijn de symbolische en laag-nieuwe unfoldings structureel bijna identiek. De laag-niveau aanpak is hier vaak sneller of vergelijkbaar, omdat de overhead van de SMT-oplosser (voor het controleren van guards) zwaarder weegt dan de winst van het samenvoegen van toestanden.
Hobbits And Orcs: Een rivieroversteekprobleem met variabele determinisme.
- Resultaat: Bij kleine boten (hoge determinisme) wint de laag-niveau aanpak. Bij grotere boten (lagere determinisme) wint de symbolische aanpak.
Mastermind: Een code-braakspel.
- Resultaat: De symbolische aanpak wint duidelijk, vooral bij een groot aantal kleuren. De grootte van de symbolische prefix blijft lineair of constant, terwijl de laag-nieuwe prefix exponentieel groeit.

Conclusie uit experimenten: De symbolische benadering is superieur bij netten met veel parallelle keuzes (niet-deterministisch in de vuurmodi). Bij sterk deterministische netten kan de overhead van de symbolische logica (SMT-oplossing) de prestaties tenietdoen.

5. Betekenis en Toekomstperspectief

Dit werk is significant omdat het de brug slaat tussen de efficiënte verificatietechnieken voor laag-niveau netten en de compacte modellering van hoog-niveau netten.

Theoretisch: Het bewijst dat complete finite prefixes mogelijk zijn voor een brede klasse van hoog-niveau netten, zelfs met oneindige toestandruimtes, mits ze "symbolisch compact" zijn.
Praktisch: Het biedt een alternatief voor het expanderen van netten, wat vaak onmogelijk is bij grote of oneindige systemen.
Toekomst: De auteurs plannen het bouwen van een symbolische reachability graph voor symbolisch compacte netten en het toepassen van deze technieken op Petri-games om symbolische strategieën te vinden.

Samenvattend biedt dit artikel een robuust theoretisch fundament en een werkend algoritme om de "state explosion" bij complexe, gekleurde Petri-netten effectief te beheersen, met een duidelijke richtlijn voor wanneer deze methode de voorkeur verdient boven traditionele laag-niveau methoden.