An Elementary Proof of the FMP for Kleene Algebra

Dit artikel presenteert een nieuw, elementair bewijs voor de eindige model-eigenschap van Kleene-algebra door transformatieautomaten te gebruiken, wat leidt tot een veralgemening van eerdere resultaten over de volledigheid van eindige relationele modellen.

De kern

Stel je voor dat je twee verschillende recepten hebt voor dezelfde taart. Het ene recept zegt: "Meng bloem, suiker en eieren, bak het 20 minuten." Het andere zegt: "Meng suiker, eieren en bloem, bak het 20 minuten." Voor een mens is het duidelijk dat dit hetzelfde is. Maar voor een computer, die alles letterlijk neemt, zijn dit twee totaal verschillende instructies.

In de wereld van informatica noemen we deze instructies programma's (of wiskundig gezien: reguliere expressies). De vraag is: hoe weten we zeker dat twee programma's echt hetzelfde doen?

Deze paper, geschreven door Tobias Kappé, gaat over een wiskundig gereedschap genaamd Kleene Algebra. Je kunt dit zien als een soort "rekenmachine voor logica" die ons helpt om te bewijzen of twee programma's equivalent zijn.

Hier is de kern van het verhaal, vertaald naar alledaags taalgebruik:

1. Het Probleem: De "Grote Boek" vs. De "Kleine Boek"

De wetenschappers hebben al lang een grote, complete lijst met regels (de "Grote Boek") die zeggen wanneer twee programma's hetzelfde zijn. Dit is de Kleene Algebra. Als je een bewijs kunt vinden in dit boek, dan zijn de programma's zeker gelijk.

Maar er is een probleem: dit boek is oneindig groot en soms heel moeilijk te doorgronden. De vraag die de auteurs zich stellen is:

"Moeten we echt naar dit enorme boek kijken, of kunnen we volstaan met een klein, handzaam boekje dat we in onze broekzak kunnen dragen?"

Dit "kleine boekje" vertegenwoordigt eindige modellen. In plaats van naar oneindig veel mogelijke scenario's te kijken, kijken we alleen naar situaties met een beperkt aantal stappen of toestanden.

2. De Vroegere Ontdekkingen

Twee andere wetenschappers, Kozen en Palka, hadden al ontdekt dat dit "kleine boekje" eigenlijk net zo goed werkt als het grote.

• Kozen zei: "Als twee programma's hetzelfde doen in de taal van reguliere expressies (de taal van computers), dan kun je dat ook bewijzen met de regels van Kleene Algebra."
• Palka zei: "En als je alleen kijkt naar eindige modellen (kleine, beperkte systemen), dan krijg je precies dezelfde resultaten!"

Dit is een enorm belangrijk idee, genaamd de Finite Model Property (FMP). Het betekent dat je niet naar oneindig hoeft te kijken om te weten of twee programma's gelijk zijn; je kunt volstaan met een eindig, beheersbaar voorbeeld.

3. Het Nieuwe Bewijs: De "Transformatie-Machine"

Tot nu toe waren de bewijzen voor deze theorieën vaak erg abstract en zwaar, gebaseerd op complexe automaten (denk aan robots die door een doolhof lopen).

Kappé heeft een nieuw, eenvoudiger bewijs bedacht. Hij gebruikt een creatieve analogie die hij "transformatie-automata" noemt.

De Analogie:
Stel je voor dat je een doolhof hebt met verschillende kamers (toestanden).

• Een programma is een reeks instructies die je door het doolhof leiden (bijv. "ga links, ga rechtdoor").
• Een transformatie is het totale effect van die instructies op het hele doolhof. Als je "ga links" doet, verandert dat de positie van alle mensen in het doolhof tegelijk.

Kappé's idee is als volgt:

1. Hij neemt een programma en bouwt er een spiegelbeeld van: een machine die niet kijkt naar waar je bent, maar naar hoe de hele machine verandert door de instructies.
2. Hij toont aan dat als je dit spiegelbeeld bekijkt, je precies kunt zien of twee programma's hetzelfde effect hebben.
3. Het mooie is: dit spiegelbeeld is altijd eindig. Het heeft maar een beperkt aantal toestanden, ongeacht hoe complex het oorspronkelijke programma is.

4. Waarom is dit belangrijk?

Dit nieuwe bewijs is als het vinden van een korte weg door een dicht bos.

• Vroeger: Je moest een enorme berg beklimmen (minimale automaten, bisimulatie) om te zien of twee programma's gelijk waren.
• Nu: Je kunt een brug gebruiken (transformatie-automata) die direct en logisch leidt tot het antwoord.

Dit betekent dat we:

1. Betrouwbare software makkelijker kunnen verifiëren. Als we een fout in een programma willen vinden, hoeven we niet naar oneindig te zoeken; we kunnen een eindig, klein voorbeeld maken dat de fout blootlegt.
2. Wiskundige theorieën beter begrijpen. Het bewijs is "elementair", wat betekent dat het minder afhankelijk is van ingewikkelde, obscure wiskundige trucs en meer gebaseerd is op heldere, logische stappen.

Samenvatting in één zin

Deze paper laat zien dat je, om te bewijzen dat twee computerprogramma's hetzelfde doen, niet hoeft te kijken naar oneindig complexe scenario's; je kunt volstaan met een simpel, eindig model dat je als een "spiegel" van het programma kunt gebruiken, en dit bewijst dat de wiskundige regels die we gebruiken altijd kloppen.

Het is een beetje alsof je ontdekt dat je niet de hele oceaan hoeft te drinken om te weten dat het water zout is; een klein glas water uit de oceaan is genoeg, zolang je maar weet hoe je dat glas moet vullen. Kappé heeft de beste manier gevonden om dat glas te vullen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "An Elementary Proof of the FMP for Kleene Algebra" van Tobias Kappé, geschreven in het Nederlands.

Probleemstelling

Kleene Algebra (KA) is een fundamenteel wiskundig raamwerk voor het redeneren over de equivalentie van reguliere expressies en programma's. De equationale theorie van KA is decibel, wat betekent dat er een algoritme bestaat om te bepalen of twee expressies gelijk zijn volgens de axioma's van KA. Dit maakt KA zeer bruikbaar in interactieve bewijshulpmiddelen (zoals Coq).

Echter, er rijzen twee belangrijke theoretische vragen:

1. Welke vergelijkingen die waar zijn in specifieke modellen (zoals eindige modellen of relationele modellen) kunnen niet worden bewezen met de algemene wetten van KA?
2. Zijn er modellen van KA die "compleet" zijn, in de zin dat ze precies de bewijsbare vergelijkingen bevatten?

Historisch gezien zijn belangrijke resultaten gevestigd:

• Kozen (1994): KA is compleet ten opzichte van het taalmodel (reguliere talen).
• Pratt (1980): KA is compleet ten opzichte van relationele modellen.
• Palka (2005): KA heeft de Finite Model Property (FMP): elke vergelijking die niet bewijsbaar is in KA, kan worden weerlegd door een eindig model.

De bestaande bewijzen voor deze resultaten (zoals die van Kozen) zijn vaak complex en maken gebruik van concepten als minimaliteit van automaten, bisimilariteit of cyclische bewijssystemen. Palka merkte op dat een onafhankelijk, elementair bewijs van de FMP zou leiden tot een nieuw perspectief op de volledigheidstheorema's, maar liet dit als toekomstwerk achter. Dit artikel vult die lacune op.

Methodologie

De auteur kiest een algebraïsche benadering die verschilt van eerdere methoden die zich baseerden op de minimaliteit van automaten of bisimilariteit. De kern van de methode bestaat uit drie pijlers:

1. Transformatie-automata (Transformation Automata):
   In plaats van reguliere expressies direct te vertalen naar eindige automaten, gebruikt de auteur transformatie-automata. Deze automata werken op de verzameling van relaties op de toestanden van een oorspronkelijke automaat. Elke toestand in een transformatie-automaton vertegenwoordigt een transformatie (relatie) die kan worden veroorzaakt door het lezen van een woord.

2. Antimirov's Constructie:
   De auteur gebruikt Antimirov's constructie om voor elke reguliere expressie $e$ een automaat $A_e$ te definiëren. De toestanden van deze automaat zijn afgeleiden (derivatives) van de expressie. Dit biedt een eindige representatie van de expressie die geschikt is voor algebraïsche manipulatie.

3. Lineaire Systemen en Oplossingen:
   Een cruciaal aspect is het gebruik van de eigenschap dat KA lineaire systemen kan oplossen. De auteur toont aan dat de "minimale oplossing" van een lineair systeem (gebaseerd op de overgangen van een automaat) overeenkomt met de reguliere expressie die de taal van die automaat beschrijft. Door dit concept toe te passen op transformatie-automata, kan men de relatie tussen expressies en hun interpretaties in eindige modellen algebraïsch analyseren.

De bewijsstrategie volgt een logische keten:

• Een expressie $e$ wordt gekoppeld aan een specifieke eindige relationele Kleene-algebra $K_e$, gebaseerd op de transformaties van de Antimirov-automaten van $e$.
• Men toont aan dat als een vergelijking $e = f$ geldt in dit specifieke eindige model $K_e$, dan moet $e$ en $f$ algebraïsch equivalent zijn ($e \equiv f$).

Belangrijkste Bijdragen

1. Onafhankelijk Elementair Bewijs van de FMP:
   De hoofdcontribution is een nieuw, elementair bewijs van de Finite Model Property voor Kleene Algebra. Dit bewijs is "elementair" omdat het niet afhankelijk is van complexe theorieën zoals bisimilariteit of minimaliteit van automaten, maar puur steunt op algebraïsche representaties (transformatie-automata) en de eigenschappen van lineaire systemen in KA.

2. Volledigheid ten opzichte van Eindige Relationele Modellen:
   Het artikel introduceert een nieuw resultaat dat de bestaande theorema's van Palka (eindige modellen) en Pratt (relationele modellen) samenvoegt. De auteur bewijst dat KA compleet is ten opzichte van eindige relationele modellen (FR). Dit betekent dat elke vergelijking die waar is in alle eindige relationele KAs, ook bewijsbaar is in de algemene KA.

3. Algebraïsche Spin op Bestaande Technieken:
   De auteur geeft een nieuwe algebraïsche interpretatie van transformatie-automata. In plaats van alleen te kijken naar de taal die wordt geaccepteerd, worden de toestanden van de automaat gezien als elementen van een monoid (relaties), wat de constructie van een eindig KA-model mogelijk maakt.

4. Formalisatie in Coq:
   Alle resultaten in het artikel zijn geformaliseerd in het interactieve bewijssysteem Coq. Dit verhoogt de betrouwbaarheid van de complexe bewijzen en biedt een referentiekader voor studenten en onderzoekers.

Resultaten

• Stelling (FMP): Als $e = f$ geldt in alle eindige Kleene-algebra's, dan is $e \equiv f$ (bewijsbaar met de axioma's van KA).
• Stelling (FRMP): Als $e = f$ geldt in alle eindige relationele Kleene-algebra's, dan is $e \equiv f$.
• Verband tussen modellen: Het artikel schetst een volledig overzicht van de implicaties tussen verschillende modellen (Taal, Star-continu, Relationeel, Eindig, Eindig-Relationeel). Het toont aan dat volledigheid voor één van deze klassen automatisch volledigheid voor de andere impliceert.
• Constructie: Voor elke expressie $e$ wordt een expliciet eindig model $K_e$ geconstrueerd dat fungeert als een "witness" voor niet-bewijsbare vergelijkingen. Als $e \not\equiv f$, dan is er een eindig model waarin ze verschillend zijn.

Betekenis en Toekomstperspectief

De betekenis van dit werk ligt op meerdere niveaus:

• Didactisch: Het biedt een "elementair" bewijs dat minder afhankelijk is van zware automata-theorie en meer steunt op algebraïsche manipulatie. Dit maakt het toegankelijker voor graduate studenten en onderzoekers die geïnteresseerd zijn in KA.
• Theoretisch: Het sluit de gaten in de literatuur door een onafhankelijk bewijs te leveren voor de FMP, zoals eerder gevraagd door Palka. Het versterkt het inzicht dat de equationale theorie van KA volledig wordt bepaald door zijn eindige modellen.
• Praktisch: De resultaten ondersteunen het gebruik van KA in bewijshulpmiddelen. Omdat de FMP geldt, kunnen tools vertrouwen op eindige counter-examples om onbewijsbaarheid aan te tonen.

Toekomstig werk:
De auteur suggereert dat deze technieken mogelijk kunnen worden uitgebreid naar:

• Concurrent Kleene Algebra (CKA): Om de volledigheid voor concurrente programma's te bewijzen, een gebied waar huidige technieken tekortschieten.
• Guarded Kleene Algebra with Tests (GKAT): Het toepassen van transformatie-automata op GKAT om betere volledigheidsresultaten te bereiken dan de huidige oneindige axiomatische schema's.
• Representatietheorie: Onderzoek naar of elke (star-continue) KA kan worden gerepresenteerd als een subalgebra van een relationele KA, analoog aan Cayley's stelling voor groepen.

Kortom, dit artikel levert een elegante, algebraïsche oplossing voor een langdurig theoretisch probleem en opent nieuwe wegen voor het redeneren over complexe programmeertalen.