Welche Algorithmen sind für die Berechnung von Craig-Interpolanten bekannt?

19

Gibt es eine Übersicht über Algorithmen zur Berechnung von Interpolanten? Was ist mit Beiträgen zu nur einem Algorithmus? Der Fall, an dem ich am meisten interessiert bin, ist und , plus der Einschränkung, dass der Interpolant so klein wie möglich ist. (Ich kenne McMillans Artikel aus dem Jahr 2005 , in dem beschrieben wird, wie man Interpolanten erhält und dabei Quantifizierer vermeidet.) $A=\lnot p\land q$ $C=q$

Hintergrund: Craigs Interpolation Satz (1957) sagt , dass , wenn , wobei ein ( fol ) Formel in und eine Formel ist , dann gibt es eine Formel , so dass und . Formel ist eine Craig-Interpolation von und $\vdash_{T_A\cup T_C}A\to C$ $A$ $T_A$ $C$ $T_C$ $B$ $\vdash_{T_A}A\to B$ $\vdash_{T_C}B\to C$ $B$ $A$ $C$ (oder in alternativen Definitionen von und ). Ein trivialer Interpolant von und ist , aber ich möchte einen kleinen Interpolanten für eine vernünftige Definition von 'klein' (wie syntaktische Größe). (Interpolanten haben viele Verwendungszwecke, und falls Sie neugierig sind, finden Sie hier einen .) $A$ $\lnot C$ $\lnot p\land q$ $q$ $q$

Motivation: Dies wäre hilfreich bei der (sehr) inkrementellen Programmüberprüfung durch Generierung von Überprüfungsbedingungen.

reference-request lo.logic proof-complexity feasible-interpolation Radu GRIGore
quelle

Es gibt verschiedenes Ergebnis über die Komplexität des Interpolant von einem gegebenen Beweis in verschiedenen Beweissystemen zu finden. In einigen schwachen Beweissystemen ist es möglich, den Interpolanten effizient zu finden (und dann sagen wir, dass das Beweissystem die realisierbare Interpolationseigenschaft erfüllt), aber stärkere Systeme haben diese Eigenschaft nicht, wenn plausible Hypothesen in der Krypto angenommen werden. Kurz I, der Algorithmus für die Interpolant zu finden , hängt von dem Proof - System verwendet wird , um zu zeigen ,

.

A \to C

$A \to C$

Kaveh

Ich muss etwas vermissen. Die triviale Interpolant

hat eine Größe 1. Wie kann es ein kleiner sein?

q

$q$

Emil Jeřábek unterstützt Monica

@ EmilJeřábek:

und

sind Metavariablen , die für Formeln stehen. Zum Beispiel könnte man

und

, wobei in diesem Fall

ist eine gute Interpolation von

p

$p$

q

$q$

p \equiv ((x = 1) \lor p r i m e (x))

$p\equiv((x=1)\lor{\it prime}(x))$

q \equiv ((x = 1) \land o d d (x))

$q\equiv((x=1)\land{\it odd}(x))$

f a l s e

${\bf false}$

\neg p \land q

$\lnot p\land q$ und

, weil

befriedigend ist. In meiner Anwendung ist

eine alte Verifizierungsbedingung , und

ist die Verifizierungsbedingung, die erhalten wurde, nachdem das Programm geringfügig bearbeitet wurde.

q

$q$

\neg p \land q

$\lnot p\land q$

p

$p$

q

$q$

Radu GRIGore

Aha. Ich bin ziemlich verwirrt von der Notation. Gibt es einen Grund , warum

sind Klein, und

Großbuchstaben?

p, q

$p,q$

A, B, C

$A,B,C$

Emil Jeřábek unterstützt Monica am

16

Schauen Sie sich die Doktorarbeit von Himanshu Jain an , die Überprüfung mittels Satisfiability Checking, Predicate Abstraction und Craig Interpolation . Er betrachtet die Leistung mehrerer grundlegender Techniken im Hinblick auf Verifikationsanwendungen und hat ein Kapitel über die Interpolation von Formeln mit linearen Gleichungen und Diophantinen.

Er befasst sich insbesondere mit der Verbindungsmethode von Bibel, die er General Matings nennt. Dies sind eher graphbasierte als formelinferenzbasierte Ansätze zur Erfüllbarkeit. Wenn Sie allgemein daran interessiert sind, lassen Sie mich Dominic Hughes 'relativ kurze (11 Seiten) Proofs ohne Syntax empfehlen .

Charles Stewart
quelle

8

Interessanterweise gibt es eine Verbindung zwischen Einschalt- und Eliminierung der Interpolationsschaltung Theorem. Zuallererst sieht der Interpolationssatz wie eine Umkehrung der Mischregeleliminierung aus, die während der Schnitteliminierung verwendet wird. Diese Eliminierung sagt:

If G |- A and D, A |- B are cut-free proofs,  
then there is a cut-free proof G, D |- B

Nun kann eine Form des Interpolationstheorems, das auf schnittfreien Beweisen basiert, wie folgt durchgeführt werden. Es ist die verkehrte Version der Beseitigung. Es beginnt mit G, D | - B und gibt G | - A und D, A | - B:

If G; D |- B is a cut free proof,  
then there is a formula A (the interpolant) 
and cut free proofs G |- A and D, A |- B,  
and A uses only propositions simultaneously from G and D

Ich setze absichtlich ein Semikolon zwischen die Prämissen G und D. Hier zeichnen wir die Linie, welche Prämissen wir als Interpolationsmittel liefern wollen und welche Prämissen wir mit dem Interpolationsmittel sehen wollen.

Wenn die Eingabe ein Freischnitt-Proof ist, ist der Aufwand des Algorithmus proportional zur Anzahl der Knoten des Freischnitt-Proofs. So ist es praktisch eine Methode linear in der Eingabe. Bei jedem Beweisschritt des Freischnitt-Beweises setzt der Algorithmus die Interpolante zusammen, indem er eine neue Verbindung einführt.

Die obige Beobachtung gilt für die einfache Interpolationskonstruktion, bei der nur vorausgesetzt wird, dass der Interpolant gleichzeitig Aussagen von G und D enthält. Interpolanten mit variabler Bedingung erfordern ein wenig mehr Schritte, da auch eine variable Behinderung erforderlich ist.

Möglicherweise besteht ein Zusammenhang zwischen der Minimalität des Cut-Free-Proofs und der Größe des Interpolanten. Nicht alle Proofs ohne Schnitte sind minimal. Beispielsweise sind einheitliche Proofs oft kürzer als geschnittene Proofs. Das Lemma für einheitliche Beweise ist ganz einfach, eine Regelanwendung der Form:

 G |- A       G, B |- C
 ----------------------
     G, A -> B |- C

Kann vermieden werden, wenn B nicht im Beweis von C verwendet wird. Wenn B nicht im Beweis von C verwendet wird, haben wir bereits G | - C und somit durch Schwächen von G, A -> B | - C. Die Interpolation Der hier erwähnte Algorithmus wird darauf nicht eingehen.

Freundliche Grüße

Referenzen: Craig's Interpolation Theorem, formalisiert und mechanisiert in Isabelle / HOL, Tom Ridge, Universität Cambridge, 12. Juli 2006 http://arxiv.org/abs/cs/0607058v1

Die obige Referenz zeigt nicht genau die gleiche Interpolation, da sie Mehrfachmengen im Abschlussteil einer Folge verwendet. Auch macht es keinen Gebrauch von Implikation. Aber es ist interessant, da es meine Behauptung der Komplexität stützt und eine mechanisierte Verifikation zeigt.

quelle

Jan, du kannst LaTeX-ähnliche Mathematik für cstheory verwenden.

Kaveh

8

Es ist über zwei Jahre her, dass diese Frage gestellt wurde, aber in dieser Zeit wurden mehr Artikel über Algorithmen zur Berechnung von Craig-Interpolanten veröffentlicht. Dies ist ein sehr aktives Forschungsgebiet und es ist nicht möglich, hier eine umfassende Liste zu erstellen. Ich habe Artikel unten eher willkürlich ausgewählt. Ich würde vorschlagen, folgenden Artikeln zu folgen, die auf sie verweisen, und ihre verwandten Arbeitsabschnitte zu lesen, um ein klares Bild der Landschaft zu erhalten.

Effiziente Interpolantengenerierung in der Modulo-Theorie der Erfüllbarkeit, Alessandro Cimatti, Alberto Griggio, Roberto Sebastiani, ACM TOCL, 2010.

Deckt die Interpolation für lineare rationale Arithmetik, rationale Differenzlogik und Ganzzahldifferenzlogik sowie für Logik mit zwei Variablen pro Ungleichung (UTVPI) ab.
Effiziente Interpolantenerzeugung in der Modulo-Linear-Integer-Arithmetik der Erfüllbarkeit, Alberto Griggio, Thi Thieu Hoa Le und Roberto Sebastiani. 2010.
Eine Kombinationsmethode zur Erzeugung von Interpolanten , Greta Yorsh und Madanlal Musuvathi. 2005.

Zeigt, wie Interpolanten in Gegenwart einer Nelson-Oppen-Theoriekombination erzeugt werden.
Bodeninterpolation für die Theorie der Gleichheit , Alexander Fuchs, Amit Goel, Jim Grundy, Sava Krstic, Cesare Tinelli. 2011.
Komplette instanziierungsbasierte Interpolation , Nishant Totla und Thomas Wies. 2012.
Interpolanten als Klassifikatoren , Rahul Sharma, Aditya V. Nori und Alex Aiken, 2012.

Vijay D
quelle

Welche Algorithmen sind für die Berechnung von Craig-Interpolanten bekannt?

Antworten: