💻 computer science

A Diagrammatic Axiomatisation of Behavioural Distance of Nondeterministic Processes

Dit artikel presenteert een correcte en volledige diagrammatische axiomatisering van gedragsafstand voor niet-deterministische processen met behulp van Milner's diagrammen en stringdiagrammen, en biedt een variabele-vrij, compositief raamwerk dat de focus verschuift van taalequivalentie naar bisimilariteit.

Oorspronkelijke auteurs: Wojciech Różowski, Robin Piedeleu, Alexandra Silva, Fabio Zanasi

Gepubliceerd 2026-05-01

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Wojciech Różowski, Robin Piedeleu, Alexandra Silva, Fabio Zanasi

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

Het Grote Plaatje: Meten hoe "verschillend" twee machines zijn

Stel je hebt twee robots. In de oude dagen van de informatica stelden we slechts een simpele vraag: "Zijn deze twee robots precies hetzelfde?" Als dat zo was, prima. Zo niet, dan werden ze als volledig verschillend beschouwd. Het was een "ja of nee"-antwoord.

Maar in de echte wereld zijn dingen zelden perfect. Misschien maakt Robot A één extra stap om links te draaien, of pauzeert Robot B een fractie van een seconde voordat hij spreekt. Ze zijn niet precies hetzelfde, maar ze zijn ook niet volledig verschillend. Ze zijn dichtbij.

Dit artikel introduceert een manier om te meten hoe dichtbij twee complexe, onvoorspelbare computerprocessen bij elkaar liggen. In plaats van een simpele "hetzelfde/verschillend"-schakelaar, creëren de auteurs een liniaal die de "afstand" tussen hen meet.

Het Probleem: Het "Kies je Eigen Avontuur"-boek

Het specifieke type computerproces dat de auteurs bestuderen, heet een Niet-deterministisch Proces. Denk hierbij aan een "Kies je Eigen Avontuur"-boek waar het verhaal op veel manieren tegelijkertijd kan vertakken.

Deterministisch: Je leest een pagina en er is slechts één volgende pagina.
Niet-deterministisch: Je leest een pagina en er zijn drie mogelijke volgende pagina's, en het verhaal kan elk van die paden inslaan.

Wanneer je twee van deze vertakkende verhaalkaarten hebt, is het vergelijken ervan moeilijk. Als ze allebei een "doodlopende weg" hebben (een plek waar het verhaal stopt) op verschillende punten, hoe ver uit elkaar liggen ze dan?

De Oplossing: String-diagrammen (De "Flowchart"-taal)

Om dit op te lossen, gebruiken de auteurs een speciale taal genaamd String-diagrammen.

De Analogie: Stel je een flowchart of een printplaat voor. Je hebt draden die binnenkomen, dozen in het midden (die dingen doen), en draden die naar buiten gaan.
Waarom ze gebruiken? Traditionele wiskunde voor deze processen gebruikt variabelen en complexe tekst (zoals algebra). String-diagrammen zijn visueel. Ze zien eruit als de daadwerkelijke stroom van het proces.
- Een doos is een actie (zoals "een knop indrukken").
- Een draad is de stroom van informatie.
- Kruisende draden betekent dingen omwisselen.
- Lussen betekenen dat het proces zichzelf herhaalt (recursie).

De auteurs betogen dat het tekenen van deze diagrammen veel gemakkelijker en intuïtiever is dan het opschrijven van complexe vergelijkingen, vooral wanneer je dingen over hen wilt bewijzen.

De Kerninnovatie: De "Afstands-liniaal"

De belangrijkste prestatie van het artikel is het creëren van een set regels (axioma's) waarmee je de afstand tussen twee diagrammen kunt berekenen zonder de computers daadwerkelijk te laten draaien.

Denk hierbij aan een wiskundig recept om verschil te meten:

Het Nulpunt: Als twee diagrammen identiek zijn (of zich precies hetzelfde gedragen), is hun afstand 0.
Het Maximumpunt: Als ze volledig ongerelateerd zijn, is de afstand 1.
De Halveringsregel: Dit is het slimme deel. Als twee processen verschillend zijn, maar je ze hetzelfde kunt laten lijken door aan beide één extra "stap" toe te voegen (zoals het indrukken van een knop), dan is de afstand tussen hen de helft van de afstand van wat er daarna komt.
- Analogie: Stel je twee hardlopers voor. Als ze momenteel op dezelfde plek staan, is de afstand 0. Als de een één stap voor is, zijn ze "dichtbij". Als de een twee stappen voor is, zijn ze "minder dichtbij". De wiskunde in het artikel zegt: Elke keer dat je een stap toevoegt aan het begin van het proces, wordt de "afstand" tussen de twee processen gehalveerd.

Hoe Ze Bewezen Dat Het Werkt

De auteurs gokten deze regels niet zomaar; ze bewezen twee kritieke dingen:

Geldigheid (De Leugen Vrijwaren): Als hun regels zeggen dat twee diagrammen "0,25 afstand" uit elkaar liggen, dan zijn ze dat echt ook 0,25. De wiskunde houdt stand.
Volledigheid (De Regels Vangen Alles): Als twee diagrammen echt 0,25 uit elkaar liggen, kunnen de regels dat getal vinden. Er zijn geen verborgen afstanden die de regels missen.

Ze deden dit door te laten zien dat elk complex diagram kan worden opgesplitst in een standaard "normale vorm" (zoals het vereenvoudigen van een breuk). Eenmaal vereenvoudigd, konden ze een wiskundige techniek gebruiken genaamd fixpunten (een berekening herhalen totdat deze stopt met veranderen) om de exacte afstand te meten.

De "Uitvouw"-truc

Een van de belangrijkste metaforen in het artikel is uitvouwen.
Stel je een verward bal van garen voor (een complex proces met lussen). De auteurs laten zien dat je deze bal kunt "uitvouwen" tot een lange, rechte lijn (een boomstructuur).

Eenmaal uitgevouwen, kun je precies zien waar de twee processen uit elkaar gaan.
Als ze na 2 stappen uit elkaar gaan, is de afstand $1/4$ (omdat $1/2 \times 1/2$ ).
Als ze na 3 stappen uit elkaar gaan, is de afstand $1/8$ .

Het artikel bewijst dat je deze "uitvouw"- en meetmethode volledig binnen de visuele taal van de string-diagrammen kunt uitvoeren, zonder ze eerst naar rommelige tekstcode te vertalen.

Samenvatting

Kortom, dit artikel geeft informatici een visuele toolkit om te meten hoe vergelijkbaar of verschillend twee onvoorspelbare computerprogramma's zijn.

Oude manier: "Zijn ze hetzelfde? Ja/Nee."
Nieuwe manier: "Hoe ver uit elkaar liggen ze? Hier is een liniaal, en hier zijn de regels om het te meten met behulp van plaatjes."

Dit is een fundamentele stap. Het bouwt vandaag geen specifieke app en repareert geen bug, maar het biedt de wiskundige basis (de liniaal en de regels) die toekomstige ingenieurs kunnen gebruiken om betere, betrouwbaardere systemen te bouwen die omgang met onzekerheid en fouten op een elegante manier aankunnen.

1. Probleemstelling

Het artikel adresseert de uitdaging van het kwantitatief vergelijken van het gedrag van niet-deterministische processen.

Context: Traditionele procesalgebra en automaattheorie vertrouwen op Booleaanse noties van equivalentie (zoals bisimilariteit en taal-equivalentie). Hoewel nuttig, zijn deze vaak te star voor moderne systemen die probabilistische of kwantitatieve aspecten omvatten, waarbij men moet meten hoe ver uit elkaar twee gedragingen liggen in plaats van alleen of ze identiek zijn.
Specifieke Kloof: Hoewel gedragsafstanden zijn bestudeerd voor probabilistische systemen en deterministische automaten (DFA), ontbreekt er een zorgvuldig onderbouwd en compleet axiomatisch raamwerk voor niet-deterministische processen (specifiek Milner's charts).
Uitdaging: Niet-determinisme verschuift de semantische focus van taal-equivalentie naar bisimilariteit. Bestaande algebraïsche syntaxen (zoals reguliere expressies met binders) worstelen om deze gedragingen compositieel vast te leggen zonder complexe substitutiemechanismen. Bovendien vereist het uitbreiden van kwantitatieve redenering naar niet-deterministische systemen het hanteren van de "Hausdorff lifting" van metrieken, wat technisch moeilijk te axiomatiseren is.

2. Methodologie

De auteurs hanteren een diagrammatische aanpak met behulp van stringdiagrammen (de grafische taal van symmetrische monoidale categorieën) om procesgedragingen te representeren en te redeneren.

Semantisch Model (Charts): Het artikel richt zich op Milner's charts, die eindig-toestandige niet-deterministische automaten (NFA) generaliseren door acceptatietoestanden te vervangen door variabele uitgangen. De semantiek wordt gedefinieerd over een categorie van reguliere gedragingen ( $\Omega$ ), uitgerust met een pseudometrische structuur.
Definitie van Metriek: De gedragsafstand wordt gedefinieerd via een coalgebraïsch raamwerk. Het maakt gebruik van:
1. Transition Lifting: Het lift een metriek op toestanden naar een metriek op transities (gelabelde randen en variabele uitgangen).
2. Hausdorff Lifting: Het lift de metriek naar verzamelingen van transities (om niet-determinisme te hanteren).
3. Fixpuntkarakterisering: De afstand is het kleinste fixpunt van een monotone operator op het traliewerk van pseudometrieken. Het wordt concreet gekarakteriseerd door de stratificatie van bisimilariteit (Hennessy-Milner logica), waarbij de afstand $2^{-n}$ is als twee processen bisimilar zijn tot diepte $n$ maar niet tot $n+1$ .
Syntax (Stringdiagrammen): De auteurs gebruiken stringdiagrammen als syntax. Deze keuze biedt:
- Vrije variabele representatie: Recursie wordt behandeld via feedbacklussen (traces) in plaats van expliciete binders en substitutie.
- Compositie Semantiek: De diagrammen mappingen natuurlijk naar de categorische structuur van reguliere gedragingen.
- Int Constructie: Om bidirectionele datastroom (inputs/outputs) en feedbacklussen te hanteren, maken de auteurs gebruik van de Int constructie om de getraceerde monoidale categorie van gedragingen om te vormen tot een compact gesloten categorie, waardoor lokale wire bending mogelijk wordt.

3. Belangrijkste Bijdragen

A. Een Kwantitatief Inferencesysteem

Het artikel stelt een reeks kwantitatieve equatieregels (inferencesysteem) voor om grenzen aan gedragsafstanden af te leiden ( $s \equiv_\epsilon t$ ).

Standaard Metrische Regels: Reflexiviteit, Symmetrie, Driehoeksongelijkheid en een "Continuïteits" regel (als $s \equiv_{\epsilon'} t$ voor alle $\epsilon' > \epsilon$ , dan $s \equiv_\epsilon t$ ).
Compositie Regels: Regels voor sequentiële compositie en parallelle compositie (tensor) die niet-expansiviteit behouden.
Domein-specifieke Regels:
- (Pref): Prefixen met een actie $a$ halveert de afstand ( $d(a.s, a.t) = \frac{1}{2}d(s, t)$ ). Dit vat de intuïtie samen dat het onderscheiden van twee processen één stap meer vereist.
- (Codel): Een diagram zonder initiële toestand (deadlock) bevindt zich op afstand 0 van de lege chart.
- Equationele Axioma's: Een set axioma's (A1-B11) die sterke bisimilariteit (afstand 0) vastlegt, inclusief wetten voor niet-deterministische keuze, het samenvoegen van variabelen en recursie (Conway-theorie axioma's).

B. Korrektheid en volledigheid

De centrale technische prestatie is het bewijs dat het inferencesysteem zowel sound (korrekt) als compleet is.

Soundness (Stelling 16): Elke afleidbare kwantitatieve vergelijking $f \equiv_\epsilon g$ is geldig (d.w.z. de werkelijke gedragsafstand $d(\llbracket f \rrbracket, \llbracket g \rrbracket) \leq \epsilon$ ).
Completeness (Stelling 31): Als de gedragsafstand tussen twee diagrammen $\leq \epsilon$ $\leq ϵ$ is, dan is de vergelijking $f \equiv_\epsilon g$ $f \equiv_{ϵ} g$ afleidbaar met behulp van de voorgestelde regels.
- Bewijstrategie: Het bewijs van volledigheid behelst het transformeren van willekeurige diagrammen naar een normaalvorm (die een eindige prechart voorstelt). Vervolgens wordt de berekening van de Hausdorff lifting en de fixpuntiteratie (Kleene's stelling) syntactisch gesimuleerd met behulp van de inferentieregels. De Continuïteits (Cont) regel is cruciaal om de kloof te dichten tussen de syntactische benadering en het exacte limiet.

C. Categorische Structuur

Het artikel stelt vast dat de categorie van reguliere gedragingen ( $\text{RegBeh}$ ) een Conway Theory is (een specifiek type getraceerde monoidale categorie) en dat de pseudometrische structuur het een verrijkte categorie maakt over de categorie van pseudometrische ruimten ( $\text{PMet}$ ). Dit garandeert dat alle categorische operaties (compositie, tensor, trace/dagger) niet-expansief zijn.

4. Resultaten

Formele Karakterisering: Het artikel biedt de eerste complete axiomatisatie van gedragsafstand voor Milner's charts (niet-deterministische processen met uitgangen).
Syntactische Simulatie van Metrieken: De auteurs demonstreren dat complexe metriekberekeningen, zoals de Hausdorff-afstand tussen verzamelingen van transities, puur kunnen worden gesimuleerd door syntactische manipulatie van stringdiagrammen.
Voorbeeldtoepassing: Het artikel bevat een gedetailleerde afleiding die laat zien hoe men bewijst dat twee specifieke charts (een met een deadlock na twee 'a's, de andere met oneindige 'a's) precies op een afstand van $1/4$ liggen. Dit wordt bereikt door de recursie uit te rollen en de (Pref) regel twee keer toe te passen.

5. Betekenis

Brug tussen Theorie en Praktijk: Door te bewegen van Booleaanse equivalentie naar kwantitatieve afstand, maakt het werk een genuanceerdere analyse van systemen mogelijk waar "bijna equivalent" een betekenisvol concept is (bijvoorbeeld bij verificatie van benaderende systemen of probabilistische systemen).
Unificerend Diagrammatisch Raamwerk: Het gebruik van stringdiagrammen vermijdt de complexiteit van variabelebinding en substitutie die voorkomt in traditionele procesalgebra's. Dit suggereert een weg naar een unificerend raamwerk voor het axiomatiseren van equivalenties en afstanden over diverse computationele modellen (deterministisch, niet-deterministisch, probabilistisch, gewogen).
Fundament voor Toekomstig Werk: Het artikel legt de basis voor het uitbreiden van deze resultaten naar gewogen transitiesystemen en probabilistische automaten, waarbij gedragsafstanden nog kritischer zijn. Het suggereert ook potentiële toepassingen in redenering over decompilatie-algoritmen en Guarded Kleene Algebra with Tests (GKAT).
Theoretische Vooruitgang: Het verbindt coalgebraïsche gedragsmetrieken, kwantitatieve equational logica en diagrammatische algebra, en laat zien hoe deze velden kunnen worden geïntegreerd om langdurige problemen in procestheorie op te lossen.

Kort samengevat, dit artikel slaagt erin de abstracte, coalgebraïsche definitie van gedragsafstand voor niet-deterministische processen te vertalen naar een concreet, diagrammatisch en volledig geaxiomatiseerd calculus, en bewijst dat kwantitatieve redenering over procesgedrag volledig kan worden uitgevoerd door syntactische manipulatie van stringdiagrammen.