Erfüllbarkeit Modulo Theories

Pieter Bach April 7, 2016 E 32 0
FONT SIZE:
fontsize_dec
fontsize_inc

In der Informatik und der mathematischen Logik, ist die Erfüllbarkeit Modulo Theories Problem ein Entscheidungsproblem für logische Formeln in Bezug auf Kombinationen von Hintergrundtheorien in der klassischen Logik erster Stufe mit Gleichheit zum Ausdruck gebracht. Beispiele von Theorien in der Regel in der Informatik verwendet, sind die Theorie der reellen Zahlen, die Theorie der ganzen Zahlen, und die Theorien der verschiedenen Datenstrukturen wie Listen, Arrays, Bitvektoren und so weiter. SMT kann als eine Form der Bedingungserfüllungsproblem und damit einer bestimmten formalisierten Ansatz Programmierung auf Constraint gedacht werden.

Grundbegriffe

Formal ein SMT-Instanz ist eine Formel, in der Logik erster Stufe, wo einige Funktions- und Prädikatensymbole haben zusätzliche Interpretationen und SMT ist das Problem der Feststellung, ob eine solche Formel ist erfüllbar. Mit anderen Worten, sich vorstellen, eine Instanz der Boolesche Erfüllbarkeit Problem, bei dem einige der binären Variablen werden durch Prädikate über einen geeigneten Satz von nicht-binären Variablen ersetzt. Ein Prädikat ist im Grunde eine Binärwert-Funktion der nicht-binären Variablen. Beispiel-Prädikate enthalten linearen Ungleichungen oder Gleichungen mit nicht interpretierten Begriffe und Funktionssymbole Diese Prädikate werden nach der Theorie gehören sie klassifiziert. Zum Beispiel sind lineare Ungleichungen über Real-Variablen mit den Regeln der Theorie der linearen Echt Arithmetik ausgewertet, während Prädikate mit uninterpretierte Bedingungen und Funktionssymbole werden nach den Regeln der Theorie der uninterpretierten Funktionen mit Gleichheit ausgewertet. Andere Theorien sind die Theorien von Arrays und Listenstrukturen, und die Theorie der Bit-Vektoren. Subtheorien sind möglich: zum Beispiel ist Differenzlogik eine Teil Theorie der linearen Arithmetik in dem jede Ungleichung eingeschränkt ist, um die Form für die Variablen und Datenkonstante aufweisen.

Die meisten SMT-Solver unterstützen nur quantifier freien Fragmente ihrer Logik.

Ausdruckskraft der SMT

Ein SMT-Instanz ist eine Verallgemeinerung einer Booleschen SAT Fall, in dem verschiedene Sätze von Variablen werden von Prädikaten aus einer Vielzahl von darunter liegenden Theorien ersetzt. Offensichtlich SMT Formeln liefern eine viel reichere Modellierungssprache als mit Boolean SAT Formeln möglich. Beispielsweise ein SMD-Formel ermöglicht es, die Datenpfad-Operationen durch einen Mikroprozessor an der Wort anstatt Bitebene modellieren.

Im Vergleich dazu wird Antwortsatz Programmierung auch Prädikate basiert. Anders als SMT, weiß Antwort-Set Programme keine Quantoren, und kann nicht einfach auszudrücken Einschränkungen wie lineare arithmetische oder Differenzlogik ASP ist bestenfalls geeignet für boolean Probleme, die für den freien Theorie der uninterpretierten Funktionen reduzieren. Umsetzung 32-Bit-Ganzzahlen als bitvectors in ASP leidet die meisten der gleichen Probleme, die frühen SMT Löser konfrontiert: "offensichtliche" Identitäten wie x + y = y + x sind schwer abzuleiten.

Constraint-Logikprogrammierung funktioniert Unterstützung für lineare arithmetische Constraints, aber in einem ganz anderen theoretischen Rahmen.

SMT-Solver Ansätze

Frühe Versuche zur Lösung von SMT-Instanzen beteiligt übersetzen sie Boolean SAT-Instanzen und Leiten Sie diese Formel in einen booleschen SAT-Solver. Dieser Ansatz, der als begierig Ansatz bezeichnet wird, hat ihre Vorzüge: durch Vorverarbeitung des SMT Formel in eine äquivalente Boolesche SAT Formel können wir bestehende Boolean SAT Solver verwenden "wie besehen" und nutzen ihre Leistung und Kapazität Verbesserungen im Laufe der Zeit . Auf der anderen Seite, der Verlust der High-Level-Semantik der zugrundeliegenden Theorien bedeutet, dass der Boolean SAT Solver muss viel härter arbeiten als nötig zu entdecken, "offensichtlich" Fakten Diese Beobachtung führte zur Entwicklung einer Reihe von SMT-Solver, dass enge Integration der Boolean Begründung eines DPLL-style-Suche mit der Theorie spezifische Löser, die Konjunktionen von Prädikaten aus einem bestimmten Theorie zu behandeln. Dieser Ansatz wird als faul Ansatz bezeichnet.

Dubbed DPLL, diese Architektur verleiht die Verantwortung der Boolean Argumentation zu der DPLL-basierte SAT Solver, die wiederum wirkt mit einem Löser für Theorie T durch eine gut definierte Schnittstelle. Die Theorie Löser braucht nur zum Überprüfen der Durchführbarkeit von Konjunktionen Th Prädikate auf sie von der SAT Löser geleitet, wie es untersucht die Booleschen Suchraum der Formel sorgen. Für diese Integration gut zu funktionieren, aber die Theorie Löser muss in der Lage, in die Ausbreitung und die Konfliktanalyse teilnehmen zu können, das heißt, muss es in der Lage, neue Fakten aus bereits etablierten Fakten ableiten, sowie prägnante Erläuterungen der Unmöglichkeit, wenn Theorie Konflikte liefern auftreten. In anderen Worten muß der Theorie Löser inkrementellen und backtrackable sein.

SMT für unentscheidbar Theorien

Die meisten der gemeinsamen SMT Ansätze unterstützen entscheidbar Theorien. Allerdings sind viele der wirklichen Systeme können nur mit Hilfe von nicht-linearen Arithmetik über den reellen Zahlen mit transzendenten Funktionen, beispielsweise modelliert werden ein Flugzeug und sein Verhalten. Diese Tatsache motiviert eine Verlängerung der SMT Problem der nichtlinearen Theorien, beispiels herausfinden, ob

woher

erfüllbar. Dann werden unentscheidbar in der Regel solche Probleme. Der erste Auftrag der Theorie der natürlichen Zahlen mit hinaus nannte Presburger Arithmetik, ist auch entscheidbar. Da eine Multiplikation mit Konstanten als verschachtelte Ergänzungen möglich sind, kann die Rechen in vielen Computerprogrammen mit Presburger arithmetischen Ausdruck gebracht werden, was zu entscheidbar Formeln.

Beispiele für SMT Löser Adressierungs Boolesche Kombinationen der Theorie Atomen aus unentscheidbaren arithmetischen Theorien über die reellen Zahlen sind absolver, die eine klassische DPLL-Architektur mit einer nicht-linearen Optimierungspaket als untergeordnete Theorie Löser verwendet und Isat, aufbauend auf einer Vereinheitlichung der DPLL SAT Lösen und Intervall Randbedingungspropagations genannt ISAT Algorithmus.

SMT-Solver

Die nachstehende Tabelle zeigt einige der Features der vielen verfügbaren SMT Löser. Die Spalte "SMT-LIB" zeigt die Kompatibilität mit dem SMT-LIB Sprache; viele Systeme mit 'ja' nur ältere Versionen von SMT-LIB zu unterstützen, oder bieten nur teilweise Unterstützung für die Sprache. Die Spalte "CVC" zeigt an Unterstützung für die CVC Sprache. Die Spalte "DIMACS" zeigt an Unterstützung für die DIMACS Format.

Projekte unterscheiden sich nicht nur in Funktionen und Leistung, sondern auch in der Überlebensfähigkeit des umgebenden Gemeinschaft, ihre laufenden Interesse an einem Projekt, und seine Fähigkeit, Dokumentation, Fehlerbehebungen, Tests und Verbesserungen beitragen.

Anwendungen

SMT-Solver sind nützlich sowohl für die Überprüfung, zum Nachweis der Korrektheit von Programmen und für die Synthese, Erzeugung von Programmfragmente durch die Suche über den Raum der möglichen Programme.

Verification

Computergestützte Überprüfung der Software-Programme verwendet häufig SMT Löser. Eine übliche Technik ist es, Voraussetzungen, Nachbedingungen, Schleifenbedingungen und Behauptungen in SMT Formeln, um festzustellen, ob alle Immobilien halten zu übersetzen.

Es gibt viele Gutachter auf der Oberseite des Z3 SMT-Solver gebaut. Boogie ist ein Zwischenverifikations Sprache, die Z3 verwendet, um automatisch zu prüfen einfache imperative Programme. Die VCC Gutachter für die gleichzeitige C verwendet Boogie sowie Dafny zwingenden Objekt-basierte Programme, Abendmahlskelch für die gleichzeitige Programme und Spec # für C #. F * ist ein abhängig typisierte Sprache, die Z3 verwendet, um Beweise zu finden; Der Compiler führt diese Beweise durch den Nachweis führenden Bytecode zu erzeugen.

  Like 0   Dislike 0
Vorherige Artikel Richard Gregory
Nächster Artikel William L. Moran
Bemerkungen (0)
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha