💻 computer science

Visualising CTL Witnesses and Counterexamples -- Extended Version

Dieser erweiterte Beitrag zur SPIN 2026 schlägt ein formales Modell für Beweise und Gegenbeispiele in CTL vor, das eine intuitive Visualisierung und menschliche Nachvollziehbarkeit ermöglicht, indem es minimale Evidenz für temporale Operatoren charakterisiert und alle Beweise liefert.

Ursprüngliche Autoren: Arend Rensink

Veröffentlicht 2026-04-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Arend Rensink

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Problem: Warum ist das System kaputt?

Stell dir vor, du hast einen riesigen, komplexen Videospiele-Code geschrieben. Du willst wissen: „Kann der Spieler das Spiel gewinnen?" oder „Ist es möglich, dass das Spiel in einer Endlosschleife stecken bleibt?"

In der Welt der Informatik gibt es zwei Sprachen, um solche Fragen zu stellen:

LTL (Lineare Zeit): Hier denkt man wie auf einer Schiene. Es gibt nur einen Weg. Wenn das Spiel nicht funktioniert, zeigt dir der Computer einfach eine Spur (eine Liste von Schritten) und sagt: „Schau her, hier ist der Weg, auf dem das Spiel kaputtgegangen ist." Das ist einfach zu verstehen.
CTL (Verzweigende Zeit): Hier ist die Welt wie ein Wald mit vielen Pfaden. An jeder Kreuzung kann der Spieler links oder rechts abbiegen. Die Frage ist nicht nur „Gibt es einen Weg?", sondern „Gibt es einen Weg, der funktioniert?" oder „Funktionieren alle Wege?".

Das Problem mit CTL ist: Wenn das Spiel nicht funktioniert, reicht eine einzelne Spur oft nicht aus, um zu erklären, warum. Man muss den ganzen Wald zeigen, um zu beweisen, dass kein Weg zum Ziel führt. Das ist für Menschen schwer zu überblicken.

Die Lösung: Der „Beweis" (Evidence)

Der Autor schlägt vor, nicht nur nach einem „Beweis für das Scheitern" (Counterexample) zu suchen, sondern nach einem allgemeinen Beweis (Evidence).

Wenn das Spiel funktioniert, ist der Beweis ein Zeuge (Witness): Ein kleiner Ausschnitt des Waldes, der zeigt: „Hier ist ein Weg, der funktioniert!"
Wenn das Spiel nicht funktioniert, ist der Beweis ein Gegenbeispiel (Counterexample): Ein Ausschnitt, der zeigt: „Hier sind alle Wege blockiert."

Das Ziel ist es, diesen Beweis so klein und übersichtlich wie möglich zu machen, damit ein Mensch ihn sofort versteht.

Die drei Zaubertricks der Visualisierung

Um diese Beweise verständlich zu machen, nutzt der Autor drei clevere Tricks:

1. Die „Abgeschlossenen Türen" (Closed States)

Stell dir vor, du zeigst jemandem einen Teil des Waldes, um zu beweisen, dass es keinen Weg zum Schatz gibt.

Ohne Trick: Du zeigst einen Pfad, der in eine Sackgasse führt. Aber der Betrachter denkt: „Moment, vielleicht gibt es ja eine geheime Tür, die du nicht gezeigt hast, durch die man doch weiterkommt?"
Mit dem Trick: Du klebst ein großes Schild „ZUGESPERRT" an die Sackgasse. Damit sagst du: „Hier gibt es keine weiteren Wege mehr. Es ist unmöglich, weiterzukommen."
In der Informatik nennt man diese Stellen geschlossene Zustände. Sie sind wie rote Ampeln, die sagen: „Hier hört die Möglichkeit auf." Das ist der Schlüssel, um komplexe CTL-Beweise klein und verständlich zu halten.

2. Die „Natürliche Erklärung" (Natural Evidence)

Manchmal ist ein mathematisch „kleinster" Beweis so abstrakt, dass er für Menschen verwirrend ist.

Beispiel: Ein Beweis sagt: „Wenn du hier langgehst, gewinnst du." Aber er zeigt nicht, warum du an den Zwischenstationen nicht verlierst.
Die Lösung: Der Autor fügt „natürliche" Details hinzu. Er zeigt nicht nur den Weg zum Sieg, sondern auch, dass an den Zwischenstationen die Regeln eingehalten wurden. Es ist wie bei einer guten Geschichte: Man braucht nicht nur das Ende, sondern auch die Logik dazwischen, damit es Sinn ergibt.

3. Der „Einzelne Atlas" (Combined Evidence)

Normalerweise müsste man für jeden einzelnen Zustand im Spiel einen kleinen Beweis zeigen. Das wären hunderte von Bildern – ein Albtraum zum Verstehen.

Die Lösung: Der Autor zeigt, dass man alle diese kleinen Beweise zu einem einzigen großen Bild zusammenfügen kann. Stell dir vor, du hast eine Landkarte, auf der für jeden Ort der Wald so farbig markiert ist, dass man sofort sieht: „Hier ist ein Weg zum Sieg" (Grün) oder „Hier ist alles blockiert" (Rot). Man muss nicht mehr zwischen vielen Bildern hin- und herspringen.

Zusammenfassung in einer Metapher

Stell dir vor, du bist ein Detektiv, der einen Mord aufklären muss (das ist das „Modell-Checking").

LTL ist wie ein Video, das den Mörder beim Verbrechen zeigt. Einfach.
CTL ist wie ein Labyrinth. Du musst beweisen, dass der Verdächtige niemals entkommen kann.
Die alte Methode war, das ganze Labyrinth zu zeigen. Zu groß, zu unübersichtlich.
Die neue Methode (dieser Papier) ist, ein Miniatur-Modell des Labyrinths zu bauen.
- Du zeigst nur die Wege, die relevant sind.
- Du verriegelst alle Türen, die nicht benutzt werden (die „geschlossenen Zustände"), damit niemand sagen kann: „Aber vielleicht gibt es noch einen anderen Weg!"
- Du fügst alles in einen einzigen Plan zusammen, damit der Chef (der Mensch) sofort sieht: „Ah, hier ist der Beweis, warum der Verdächtige gefangen ist."

Fazit

Dieses Papier sagt im Grunde: „Wir können die komplexen Beweise für Computer-Systeme so aufbereiten, dass sie so einfach zu verstehen sind wie eine einfache Wegbeschreibung. Wir nutzen geschlossene Türen, um Unmöglichkeiten zu zeigen, und fügen alles in ein einziges, klares Bild zusammen."

Das ist ein großer Schritt, damit nicht nur Computer, sondern auch Menschen verstehen, warum ihre Software funktioniert oder warum sie versagt.

Titel: Visualisierung von CTL-Zeugen und Gegenbeispielen – Erweiterte Version

Autor: Arend Rensink (Universität Twente)

1. Problemstellung

Die Arbeit adressiert ein fundamentales Defizit in der Modellprüfung (Model Checking) für die Computation Tree Logic (CTL) im Vergleich zur Linear Temporal Logic (LTL).

LTL-Vorteil: Bei LTL ist das Konzept eines Gegenbeispiels (Counterexample) intuitiv und einfach zu visualisieren: Es handelt sich um einen einzelnen Pfad (Trace), der die Eigenschaft verletzt.
CTL-Herausforderung: CTL ist eine Logik verzweigter Zeit (branching time). Die Nicht-Erfüllung einer Eigenschaft kann nicht durch einen einzelnen Pfad erklärt werden, sondern erfordert oft die Betrachtung einer Teilmenge der verzweigenden Struktur des Modells.
Fehlende Dualität: Während in LTL ein Gegenbeispiel für $\phi$ ein Pfad ist, der $\neg \phi$ erfüllt, ist dies in CTL komplexer. In CTL ist die Verletzung einer Eigenschaft äquivalent zur Erfüllung ihrer Negation. Daher gibt es keinen strikten Unterschied zwischen "Zeugen" (Witness, für erfüllte Eigenschaften) und "Gegenbeispielen" (Counterexample, für verletzte Eigenschaften).
Ziel: Das Papier definiert einen einheitlichen Begriff der Evidenz (Evidence), der sowohl als Zeuge für erfüllte als auch als Gegenbeispiel für verletzte CTL-Eigenschaften dient, und entwickelt Methoden zur effektiven Visualisierung dieser Evidenz für das menschliche Verständnis.

2. Methodik und formale Grundlagen

2.1 Modellierung und Semantik

Das Papier verwendet eine erweiterte Definition von Kripke-Strukturen:

Modelle: Ein Modell $M = \langle S, C, R, L \rangle$ besteht aus Zuständen $S$ , einer Relation $R$ , einer Beschriftungsfunktion $L$ und einer Teilmenge geschlossener Zustände $C \subseteq S$ .
Geschlossene Zustände (Closed States): Dies ist eine technische Neuerung. Ein Zustand ist "geschlossen", wenn alle seine ausgehenden Transitionen im Modell explizit vorhanden sind. Dies verhindert, dass in Supermodellen (Erweiterungen des Modells) neue Transitionen hinzugefügt werden, die die Evidenz ungültig machen würden.
Evidenz: Eine Evidenz für eine Aussage $(s, \phi, b)$ (wobei $b \in \{0,1\}$ ) ist ein Teilmodell, das genügend Informationen über die Unterformeln von $\phi$ enthält, um die Gültigkeit der Aussage in jedem konsistenten Supermodell zu garantieren.

2.2 Minimale Evidenz

Das Papier charakterisiert die minimale Evidenz für die Kernoperatoren von CTL (EX, EU, EG).

Zeugen (Witnesses):
- Für $EX \psi$ : Ein einzelner Nachfolger, der $\psi$ erfüllt.
- Für $E \psi_1 U \psi_2$ : Ein endlicher Pfad von offenen Zuständen, der mit einem Zustand endet, der $\psi_2$ erfüllt, während alle vorherigen $\psi_1$ erfüllen.
- Für $EG \psi$ : Ein Pfad (endlich oder unendlich), der nur Zustände enthält, die $\psi$ erfüllen. Ein endlicher Pfad muss in einem geschlossenen Zustand enden, um zu garantieren, dass er nicht erweitert werden kann.
Gegenbeispiele (Counterexamples):
- Für $EX \psi$ : Der Zustand muss geschlossen sein, und alle Nachfolger müssen $\psi$ verletzen.
- Für $E \psi_1 U \psi_2$ : Alle maximalen Pfade müssen entweder in einem Zustand enden, der $\psi_2$ verletzt, oder unendlich in Zuständen verlaufen, die $\psi_1$ verletzen (ohne $\psi_2$ zu erreichen).
- Für $EG \psi$ : Alle maximalen Pfade müssen einen Zustand erreichen, der $\psi$ verletzt.

2.3 Beweise (Proofs)

Ein Beweis für ein Modell ist eine Zuordnung, die jedem Zustand und jeder zusammengesetzten Formel eine minimale Evidenz zuordnet. Dies ermöglicht es, die Korrektheit des gesamten Modellprüfungsergebnisses schrittweise zu rekonstruieren.

3. Schlüsselbeiträge

Formale Definition von Evidenz: Einführung eines einheitlichen Begriffs, der Zeugen und Gegenbeispiele abdeckt, basierend auf der Semantik von Teilmodellen und geschlossenen Zuständen.
Charakterisierung minimaler Evidenz: Herleitung notwendiger und hinreichender Bedingungen für minimale Evidenz (unter der Annahme "unbeschränkter" Unterformeln), dargestellt in Tabellenform für Zeugen und Gegenbeispiele.
Konzept der "Natürlichen Evidenz" (Natural Evidence):
- Minimale Evidenz kann formal korrekt, aber für Menschen schwer verständlich sein (z. B. wenn Beschriftungen von Unterformeln in nicht-terminalen Zuständen fehlen).
- Natürliche Evidenz fügt diese fehlenden lokalen Informationen hinzu, um die Intuition zu unterstützen, ohne die Minimalität im Sinne der Struktur zu verlieren.
Kombinierte Evidenz:
- Statt für jeden Zustand und jede Formel ein separates Bild zu zeigen, wird gezeigt, dass sich die Evidenz für eine feste Formel über alle Zustände eines Modells in einem einzigen kombinierten Modell zusammenfassen lässt.
- Dies reduziert die Anzahl der benötigten Visualisierungen drastisch (von "pro Zustand/Formel" auf "pro temporaler Operator").
Implementierung und Visualisierung: Vorstellung eines interaktiven Demonstrators, der auf dem Abstract Syntax Tree (AST) der Formeln basiert.
- Visualisierungstechniken: Nutzung von Farben (Grün/Rot/Grau) für Wahrheitswerte, gestrichelte Linien für offene Zustände und spezielle Muster für geschlossene Zustände oder unendliche Pfade.
- Lokale Geschlossenheit (Local Closure): Integration der Evidenz für nicht-temporale Operatoren direkt in die Darstellung, um Verwirrung zu vermeiden.

4. Ergebnisse

Die Arbeit liefert formale Beweise (im Anhang), dass die definierten Bedingungen für minimale Evidenz korrekt sind.
Es wird gezeigt, dass kombinierte Evidenz immer existiert und dass sie für die Operatoren EU und EG minimal sein kann.
Die Visualisierung demonstriert, wie komplexe CTL-Eigenschaften (wie $EG(\neg win \land EF win)$ ) durch die Darstellung von geschlossenen Zuständen und minimalen Pfaden intuitiv erklärbar gemacht werden können.
Der Ansatz zeigt, dass die Verwendung geschlossener Zustände effizienter ist als der Vergleich mit Simulationen, da er direkt auf der Struktur des geprüften Modells operiert und negative Informationen (fehlende Transitionen) kompakt kodiert.

5. Bedeutung und Ausblick

Menschliches Verständnis: Der Hauptbeitrag liegt in der Brücke zwischen der formalen Komplexität von CTL-Modellprüfung und der menschlichen Fähigkeit, diese Ergebnisse zu interpretieren. Durch die Visualisierung von "Warum" eine Eigenschaft gilt oder nicht gilt, wird die Debugging-Fähigkeit von Systementwicklern verbessert.
Unterschied zu LTL: Das Papier etabliert, dass CTL-Gegenbeispiele keine einfachen Pfade, sondern strukturelle Teilmodelle sind, die oft geschlossene Zustände enthalten müssen, um ihre Gültigkeit zu sichern.
Zukünftige Forschung:
- Übertragung der Konzepte auf ausdrucksstärkere Logiken wie CTL*.
- Untersuchung von Simulationsrelationen in Anwesenheit geschlossener Zustände (z. B. durch Bisimulation auf geschlossenen Zuständen).

Fazit: Das Papier liefert eine fundierte theoretische Basis und eine praktische Methode zur Generierung und Visualisierung von Beweisen für CTL-Modellprüfung. Es löst das Problem der Unanschaulichkeit von CTL-Gegenbeispielen durch die Einführung geschlossener Zustände und das Konzept der natürlichen, kombinierten Evidenz.