💻 computer science

Computing Witnesses Using the SCAN Algorithm

Dieser Beitrag erweitert den auf Sättigung basierenden SCAN-Algorithmus zur Elimination von Quantoren zweiter Ordnung, um Zeugen für Quantoren zweiter Ordnung zu berechnen, die logisch äquivalente Formeln erster Ordnung ergeben, und stellt eine Prototyp-Implementierung des Verfahrens vor.

Ursprüngliche Autoren: Fabian Achammer, Stefan Hetzl, Renate A. Schmidt

Veröffentlicht 2026-05-01

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Fabian Achammer, Stefan Hetzl, Renate A. Schmidt

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

Stellen Sie sich vor, Sie haben ein komplexes Rezept (eine logische Formel), das eine geheime Zutat enthält, nennen wir sie „Zutat X". Sie wissen nicht, was „Zutat X" ist, aber Sie wissen, dass das Rezept perfekt funktioniert, wenn Sie eine Version davon verwenden.

Das Problem:
Normalerweise verwenden Logiker, wenn sie „Zutat X" entfernen wollen, um zu sehen, was das Rezept tatsächlich ist, ohne das Geheimnis, eine Methode namens Second-Order Quantifier Elimination (SOQE). Das ist wie der Versuch, das fertige Gericht zu beschreiben, ohne jemals die geheime Zutat zu erwähnen. Manchmal kann man dies perfekt tun. Aber oft sagt die Mathematik: „Wir können das Ergebnis beschreiben, aber wir können Ihnen nicht genau sagen, was die geheime Zutat war."

Die neue Entdeckung (WSOQE):
Dieser Artikel stellt ein neues, ehrgeizigeres Ziel vor, das Witnessed Second-Order Quantifier Elimination (WSOQE) genannt wird. Anstatt nur das fertige Gericht zu beschreiben, wollen die Autoren das exakte Rezept für „Zutat X" (den „Zeugen") finden, das alles zum Funktionieren bringt. Sie wollen sagen: „Zutat X ist eigentlich nur 'Zucker'."

Das Werkzeug: Der SCAN-Algorithmus
Die Autoren verwenden ein berühmtes Werkzeug namens SCAN-Algorithmus. Stellen Sie sich SCAN als einen riesigen, automatisierten Küchenroboter vor, der Ihr Rezept nimmt, es in winzige Schritte zerlegt und versucht, „Zutat X" zu entfernen, indem er die anderen Zutaten mischt und kombiniert, bis das Geheimnis nicht mehr benötigt wird.

Was dieser Artikel hinzufügt:
Der ursprüngliche SCAN-Roboter war großartig darin, die geheime Zutat zu entfernen und Ihnen das Endergebnis mitzuteilen, aber er warf die Notizen darüber, wie er es getan hat, weg. Er behielt das „Rezept für Zutat X" nicht bei.

Die Autoren, Fabian Achammer, Stefan Hetzl und Renate A. Schmidt, haben den Roboter verbessert (und die neue Version WSCAN genannt). Jetzt führt der Roboter während seiner Arbeit ein detailliertes Tagebuch über jeden Schritt. Am Ende nutzt er dieses Tagebuch, um rückwärts zu arbeiten und das exakte Rezept für „Zutat X" wiederherzustellen.

Wie sie es tun (Die „Detektiv"-Analogie):

Die Aufräumarbeiten: Der Roboter beginnt mit einem chaotischen Haufen von Hinweisen (Klauseln). Er führt logische Schritte durch (wie das Lösen eines Puzzles), um „Zutat X" zu eliminieren.
Das Tagebuch: Jedes Mal, wenn der Roboter einen Hinweis löscht, weil er nicht mehr benötigt wird, notiert er, warum er ihn gelöscht hat.
Die Reverse Engineering: Sobald der Roboter fertig ist und „Zutat X" verschwunden ist, schauen sich die Autoren das Tagebuch an. Sie arbeiten vom sauberen Ergebnis rückwärts zum chaotischen Anfang. Durch Umkehren der Logik der Schritte des Roboters können sie eine Formel erstellen, die exakt wie „Zutat X" wirkt.

Das Problem „Unendlich" vs. „Endlich":
Manchmal wird das Rezept für „Zutat X", wenn der Roboter versucht, es herauszufinden, unendlich lang (wie eine Geschichte, die nie endet).

Die Lösung: Die Autoren haben eine spezielle Bedingung namens „acyclic purification" (azyklische Bereinigung) gefunden. Stellen Sie sich einen Graphen vor, bei dem jeder Schritt im Prozess des Roboters ein Knoten ist. Wenn der Graph keine Schleifen hat (er ist „azyklisch"), ist garantiert, dass das Rezept für „Zutat X" kurz und endlich ist. Wenn es Schleifen gibt, kann das Rezept unendlich sein.
Das Ergebnis: Sie entwickelten eine Methode, um zu prüfen, ob der Prozess schlaufenfrei ist. Wenn ja, können sie ein einfaches, endliches „erstes Ordnung"-Rezept für die geheime Zutat erstellen. Wenn nicht, können sie immer noch ein Rezept erstellen, aber es könnte ein unendliches sein (oder ein „Fixpunkt-Rezept", was eine ausgefallene Art zu sagen ist: „ein Rezept, das auf sich selbst verweist, um weiterzugehen").

Echte Beispiele, die erwähnt werden:
Der Artikel spricht nicht nur über Theorie; sie testeten ihren Roboter an 44 verschiedenen logischen Rätseln.

Erreichbarkeit in Graphen: Sie nutzten ihn, um ein Problem beim Navigieren auf einer Karte zu lösen. Stellen Sie sich eine Karte mit Städten und Straßen vor, und Sie wollen eine Menge von Städten finden, die Sie ab Stadt A erreichen können, ohne Stadt B zu berühren. Der Roboter fand erfolgreich die genaue Regel (den „Zeugen"), die definiert, welche Städte sicher zu besuchen sind.
Gleichheit: Sie zeigten, dass der Roboter Regeln handhaben kann, bei denen Dinge „gleich" sind (wie $a = b$ ), was das Puzzle schwieriger macht, aber der Roboter es dennoch schafft, das Rezept der geheimen Zutat zu finden.

Das Fazit:
Dieser Artikel nimmt ein bestehendes logisches Werkzeug (SCAN), das gut darin war, unbekannte Variablen zu entfernen, und verbessert es so, dass es diese nicht nur entfernt, sondern auch genau aufdeckt, was diese Variablen gewesen sein müssen. Er schließt die Lücke zwischen „eine Lösung finden" und „die spezifische Definition des Unbekannten finden", bietet eine Prototyp-Implementierung, die an realen Beispielen funktioniert, gibt jedoch zu, dass das Rezept für das Unbekannte manchmal zu komplex sein kann, um es in einem einzigen Satz aufzuschreiben.

1. Problemstellung

Der Artikel adressiert die Eliminierung von Quantoren zweiter Ordnung (SOQE), das Problem, eine logisch äquivalente Formel erster Ordnung $\psi$ für eine gegebene Formel zweiter Ordnung $\exists X \phi$ (wobei $\phi$ erster Ordnung ist) zu finden. Während SOQE im Allgemeinen unentscheidbar ist, existieren praktische Algorithmen für spezifische Unterklassen.

Die Autoren führen ein allgemeineres Problem ein, das als Witnessed Second-Order Quantifier Elimination (WSOQE) bezeichnet wird. Anstatt nur eine äquivalente Formel erster Ordnung zu finden, besteht das Ziel darin, einen Witness (Zeugen) zu finden: ein Tupel von Prädikaten erster Ordnung $\alpha$ , sodass:
$\exists X \phi \equiv \phi[X \leftarrow \alpha]$
Dies bedeutet, dass die Formel zweiter Ordnung äquivalent zur Formel erster Ordnung ist, die durch Ersetzen der Prädikatsvariablen $X$ durch spezifische Definitionen erster Ordnung $\alpha$ erhalten wird.

Bedeutung von WSOQE:

Es überbrückt die Lücke zwischen SOQE und Formelgleichungen (FEQ) (Finden von $\alpha$ , sodass $\models \phi[X \leftarrow \alpha]$ ).
Es ist entscheidend für Anwendungen in der Wissensrepräsentation (Vergessen/Projektion), der modalen Korrespondenztheorie und der Programmverifikation (Finden von Schleifeninvarianten).
Im Gegensatz zur Standard-SOQE, die nur das Ergebnis liefert, liefert WSOQE die Definition der eliminierten Prädikate und bewahrt die Struktur der Wissensbasis.

2. Methodik: Der WSCAN-Algorithmus

Die Autoren schlagen WSCAN vor, eine Erweiterung des bestehenden SCAN-Algorithmus (ein auf Sättigung basierender Theorembeweiser für SOQE). Die Kernmethodik umfasst zwei Hauptphasen:

A. Die SCAN-Ableitung

Der Algorithmus operiert auf Klauselmengen. Er transformiert die Eingabeformel in eine klauselformale Normalform und führt einen Sättigungsprozess unter Verwendung eines spezifischen Inferenzkalküls $\mathcal{I}$ durch:

Constraint-Resolution & Faktorisierung: Anstelle der Standard-Unifikation führen diese Regeln Ungleichheits-Constraints (z. B. $t \not\simeq t'$ ) zwischen Termen ein.
Constraint-Eliminierung: Vereinheitlicht Terme, um Constraints zu entfernen.
Löschregeln:
- Erweiterte Reinheits-Löschung: Entfernt Klauseln, die $X$ enthalten, wenn $X$ nur mit einer Polarität auftritt (alle positiv oder alle negativ).
- Gereinigte Klausel-Löschung: Entfernt eine Klausel $P$ , die $X$ enthält, wenn „hinreichend viele" Inferenzen durchgeführt wurden, sodass die verbleibende Klauselmenge die Resolutionshülle von $P$ logisch impliziert. Dies wird über ein Kriterium der Vorwärtsredundanz formalisiert, das Variablenelimination und Subsumption beinhaltet.

Der Prozess wird fortgesetzt, bis alle $X$ -Literalien eliminiert sind, was zu einer Klauselmenge erster Ordnung $N^*$ führt, die äquivalent zu $\exists X N$ ist.

B. Witness-Konstruktion (Bottom-Up)

Der neuartige Beitrag ist die Extraktion eines Witnesses $\sigma$ aus der Ableitungshistorie. Der Algorithmus konstruiert den Witness rückwärts (vom Endzustand zum Anfangszustand):

Basisfall: Wenn die finale Klauselmenge $N_m$ kein $X$ enthält, ist die Identitätssubstitution ein Witness.
Induktiver Schritt: Für jeden Ableitungsschritt $S_i$ $S_{i}$ , der $N_{i-1}$ $N_{i - 1}$ in $N_i$ $N_{i}$ transformiert, berechnet der Algorithmus eine Substitution $\tau_{S_i}$ $τ_{S_{i}}$ , sodass, wenn $\sigma_i$ $σ_{i}$ ein Witness für $N_i$ $N_{i}$ ist, dann $\tau_{S_i}\sigma_i$ $τ_{S_{i}} σ_{i}$ ein Witness für $N_{i-1}$ $N_{i - 1}$ ist.
- Für Standard-Inferenzschritte (Resolution, Faktorisierung usw.) ist $\tau$ die Identität.
- Für Erweiterte Reinheits-Löschung setzt $\tau$ $X$ auf $\top$ oder $\bot$ , abhängig von der Polarität.
- Für Gereinigte Klausel-Löschung (der komplexe Fall) konstruiert der Algorithmus einen Witness basierend auf der lokalen Resolutionshülle der gelöschten Klausel.

C. Umgang mit unendlichen Witnesses

Die Resolutionshülle, die für gereinigte Klauseln verwendet wird, kann unendlich sein, was zu unendlichen Witnesses (ausgedrückt als unendliche Konjunktionen) führt. Der Artikel stellt zwei Lösungen vor:

Fixpunkt-Witnesses: Der unendliche Witness wird als größter Fixpunkt ($gfp$) in der Fixpunktlogik ausgedrückt. Dies bietet eine endliche Darstellung der potenziell unendlichen Definition.
Witnesses erster Ordnung (Azyklische Bedingung): Die Autoren definieren eine Bedingung namens $k$ -azyklisch gereinigt. Wenn der „Bereinigungs-Subsumptionsgraph", der mit einem Löschschritt verbunden ist, azyklisch ist, kann der Witness als endlicher, Prädikat erster Ordnung unter Verwendung einer beschränkten Iteration der Resolutionshülle berechnet werden.

3. Hauptbeiträge

WSCAN-Algorithmus: Eine vollständige Methode zur Berechnung von Witnesses für SOQE auf Klauselmengen, die den SCAN-Algorithmus erweitert.
Korrektheitsbeweise:
- Beweis, dass die konstruierte Substitution $\sigma$ ein gültiger Witness ist ( $\exists X N \equiv N\sigma$ ).
- Ein neuer Korrektheitsbeweis für den ursprünglichen SCAN-Algorithmus, abgeleitet aus der Logik der Witness-Konstruktion.
Garantie für Witnesses erster Ordnung: Identifizierung der Bedingung der azyklischen Bereinigung, die garantiert, dass der resultierende Witness eine Formel erster Ordnung ist (Vermeidung unendlicher oder Fixpunkt-Ausdrücke).
Erweiterung des Ackermannschen Lemmas: Die Autoren beweisen, dass ihre Methode das Ackermannsche Lemma (eine klassische Methode für SOQE) umfasst und auf Fälle erweitert, in denen das Prädikat mit gemischter Polarität auftritt.
Umgang mit Hintergrundtheorien: Die Methode wurde erweitert, um Gleichheitslogik (via Paramodulation) und Hintergrundtheorien erster Ordnung zu behandeln, wodurch sie Graph-Erreichbarkeitsprobleme und andere eingeschränkte Horn-Klausel-Probleme lösen kann.
Prototyp-Implementierung: Eine Prototyp-Implementierung im Softwarepaket GAPT (General Architecture for Proof Theory) (Version 2.19.0).

4. Ergebnisse und Evaluation

Implementierung: Der Prototyp wurde an 44 Beispielen (aus der Literatur und selbst erstellt) getestet.
Leistung:
- SCAN-Ableitungen wurden für 90,9 % der Beispiele (40/44) innerhalb eines 10-Sekunden-Timeouts gefunden.
- Die Witness-Berechnung war extrem schnell (durchschnittlich 0,619 ms) im Vergleich zum Finden der Ableitung (durchschnittlich 375 ms).
- Die Witness-Größen waren im Allgemeinen klein (durchschnittlich 6,9 Symbole).
Fähigkeiten: Das System berechnete erfolgreich Witnesses erster Ordnung für Ableitungen, die zuvor unendliche Witnesses lieferten oder Fixpunktlogik erforderten, speziell in Fällen, die azyklische Bereinigungsgraphen betrafen.
Einschränkungen:
- Die Methode erfordert, dass die Eingabe eine Klauselmenge ist (universell quantifizierte Domänenvariablen).
- Sie kann keine Fälle behandeln, in denen Skolemisierung erforderlich ist und nicht rückgängig gemacht werden kann (z. B. $\exists X \exists u \exists v (X(u) \land \neg X(v))$ ), da der resultierende Witness Skolem-Konstanten enthalten würde, die nicht in der ursprünglichen Sprache vorhanden sind.
- Der Suchraum für Ableitungen kann groß sein; die aktuelle Implementierung verwendet Backtracking, ist jedoch nicht für massive Klauselmengen optimiert.

5. Bedeutung

Diese Arbeit ist bedeutend, weil sie den SCAN-Algorithmus von einem Werkzeug, das lediglich Quantoren eliminiert, in eines verwandelt, das die Definitionen der eliminierten Prädikate synthetisiert.

Theoretische Brücke: Sie vereint die Bereiche der Eliminierung von Quantoren zweiter Ordnung (SOQE) und Formelgleichungen (FEQ) und zeigt, dass sie zwei Seiten derselben Medaille sind.
Praktische Anwendung: Durch die Bereitstellung expliziter Definitionen erster Ordnung (Witnesses) ist die Methode direkt anwendbar auf:
- Wissensrepräsentation: Erstellen von uniformen Interpolanten und Vergessen von Prädikaten unter Beibehaltung der logischen Struktur.
- Verifikation: Automatisches Generieren von Schleifeninvarianten für die Programmverifikation (Lösen eingeschränkter Horn-Klauseln).
- Modale Logik: Berechnung von Korrespondenzaxiomen für modale Logiken.

Der Artikel stellt fest, dass für eine breite Klasse von Ableitungen (jene mit azyklischen Bereinigungsgraphen) das komplexe Problem zweiter Ordnung auf die Suche nach einem endlichen, Witness erster Ordnung reduziert werden kann, was ein leistungsfähiges neues Werkzeug für das automatisierte Schließen bietet.