Propositional Dynamic Logic

Eintragsnavigation

• Eintragsinhalt
• Literaturverzeichnis
• Akademische Werkzeuge
• Freunde PDF Vorschau
• Autor und Zitierinfo
• Zurück nach oben

Propositional Dynamic Logic

Erstveröffentlichung Do 1. Februar 2007; inhaltliche Überarbeitung Fr 25 Jan 2019

Logik von Programmen sind modale Logiken, die sich aus der Idee ergeben, jedem Computerprogramm α einer Programmiersprache eine Modalität [α] zuzuordnen. Diese Idee stammt aus der Reihe von Werken von Engeler [1967], Hoare [1969], Yanov [1959] und anderen, die logische Sprachen formulierten und studierten, in denen die Eigenschaften von Programmverbindungen ausgedrückt werden können. Die zuerst von Salwicki [1970] entwickelte algorithmische Logik (AL) und die von Pratt [1976] ausgearbeitete dynamische Logik (DL) sind die richtige Fortsetzung dieser Arbeiten. Wir werden uns hier auf DL konzentrieren. Die zahlreichen Arbeiten zu DL und seinen Varianten sowie seine vielfältigen Anwendungen in der Programmverifizierung und in Datenstrukturen zeigen, dass es ein nützliches Werkzeug zur Untersuchung der Eigenschaften von Programmen darstellt. Pratt entschied sich dafür, DL auf der Ebene erster Ordnung darzustellen.und es war seine Arbeit, die Fischer und Ladner [1979] dazu veranlasste, einige Jahre später die Satzvariante von DL zu definieren. Dieser Artikel enthält eine Einführung in PDL, die Aussagenvariante von DL.

• 1. Einleitung

• 2. Definitionen und grundlegende Ergebnisse

  • 2.1 Syntax und Semantik
  • 2.2 Axiomatisierung und Vollständigkeit
  • 2.3 Entscheidbarkeit und Komplexität

• 3. Strukturierte Programmierung und Richtigkeit der Programme

  • 3.1 Hoare-Kalkül
  • 3.2 Hoare-Kalkül und PDL
  • 3.3 Völlige Richtigkeit

• 4. Einige Varianten

  • 4.1 PDL ohne Tests
  • 4.2 PDL mit Umkehrung
  • 4.3 PDL mit Wiederholung und Schleife
  • 4.4 PDL mit Schnittpunkt
• 5. Schlussfolgerung
• Literaturverzeichnis
• Akademische Werkzeuge
• Andere Internetquellen
• Verwandte Einträge

1. Einleitung

Dynamic Logics (DL) sind modale Logiken zur Darstellung der Zustände und Ereignisse dynamischer Systeme. Die Sprache von DLs ist sowohl eine Assertionssprache, die Eigenschaften von Berechnungszuständen ausdrücken kann, als auch eine Programmiersprache, die Eigenschaften von Systemübergängen zwischen diesen Zuständen ausdrücken kann. DLs sind Logik von Programmen und ermöglichen es, über Sachverhalte, Prozesse, Änderungen und Ergebnisse zu sprechen und zu argumentieren.

Pratts ursprüngliche dynamische Logik von Programmen war eine modale Logik erster Ordnung. Propositional Dynamic Logic (PDL) ist das aussagekräftige Gegenstück dazu. Es wurde in Fischer und Ladner [1979] als eigenständige Logik dargestellt. Da die Sprache der PDL aussagekräftig ist, werden keine Begriffe, Prädikate oder Funktionen verwendet. Daher gibt es in PDL zwei syntaktische Kategorien: Sätze und Programme.

Um Aussagen in PDL einen Sinn zu geben, arbeiten wir normalerweise mit einer abstrakten Semantik in Bezug auf Labeled Transition Systems (LTS). LTS können als Verallgemeinerung von Kripke-Modellen angesehen werden, bei denen Übergänge zwischen Welten oder Zuständen durch Namen von Atomprogrammen „gekennzeichnet“werden. Eine Bewertung gibt für jeden Staat an, welche Aussagen darin wahr sind. Ein mit π bezeichneter Übergang von einem Zustand x zu einem mit y bezeichneten Zustand x R (π) y oder (x, y) ∈ R (π) zeigt an, dass ab x eine mögliche Ausführung des Programms π endet in y. Wenn der Satz A in y wahr ist, dann ist die Formel A in x wahr: dh im Zustand x gibt es eine mögliche Ausführung des Programms α, die in einem Zustand endet, der A erfüllt. Man erkennt in einer Modalität, die an die Modalität der Möglichkeit (oft erwähnt ◊) der Modallogik erinnert. Nicht überraschend,es gibt auch einen entsprechenden Begriff der Notwendigkeit (dessen Modalität oft erwähnt wird □). Die Formel [π] A ist im Zustand x wahr, wenn A in jedem Zustand wahr ist, der von x durch einen mit π bezeichneten Übergang erreichbar ist.

Die möglichen Ausführungen komplexer Programme können als nächstes kompositorisch definiert werden. Zum Beispiel ist ein Programm "zuerst α, dann β" ein komplexes Programm, genauer gesagt eine Sequenz. Eine mögliche Ausführung kann in einer LTS dargestellt werden, indem ein zweistufiger Übergang gebildet wird - dann ein Übergang, der durch R (α; β) zwischen den Zuständen x und x 'bezeichnet werden kann: Es gibt eine mögliche Ausführung in x des Programms α, das in einem Zustand y endet, und in y gibt es eine mögliche Ausführung des Programms β, das in x 'endet. Wenn der Satz A in x 'wahr ist, dann ist die Formel A im Zustand x wahr. Die Programme α und β könnten selbst ein komplexes Programm sein. Noch mehr Programme können mit mehr Konstrukten ausgedrückt werden, die wir zu gegebener Zeit präsentieren werden.

Ein Programm wird dann in einer erweiterten Weise gesehen: Es ist eine binäre Beziehung zwischen Zustandspaaren eines LTS. Genau genommen ist es die Menge von Paaren der Form (x, y), so dass das Programm im Zustand x ausgeführt werden kann und zum Zustand y führen kann. Andererseits ist ein Satz eine Aussage über einen Staat; es ist entweder wahr oder falsch in einem Zustand. Ein Satz kann also auch in erweiterter Weise gesehen werden: die Menge der Zustände des LTS, in denen er wahr ist.

Mit dem Akronym PDL beziehen wir uns hier genau auf die aussagekräftige dynamische Logik mit den folgenden Programmkonstrukten: Sequenz, nicht deterministische Auswahl, unbegrenzte Iteration und Test. Wir präsentieren es in Abschnitt 2 zusammen mit einigen Eigenschaften und grundlegenden Ergebnissen. Insbesondere werden wir uns mit seiner Axiomatisierung und seiner Entscheidbarkeit befassen.

Der Hoare-Kalkül von Hoare [1969] ist ein Meilenstein für die Logik von Programmen. Es betrifft die Wahrheit von Aussagen der Form {A} α {B} - was bedeutet, dass das Programm α mit der Vorbedingung A immer B als Nachbedingung hat - und axiomatisch definiert ist. Es kommt aus dem Mangel an rigorosen Methoden, über die Eigenschaften von Programmen nachzudenken und damit der Aktivität des Programmierens einen bestimmten Platz im Bereich der Wissenschaft einzuräumen. Burstall [1974] erkannte die Analogie zwischen Modallogik und Argumentation über Programme, aber die eigentliche Arbeit daran begann mit Pratt [1976], als sie ihm von R. Moore, einem seiner damaligen Studenten, vorgeschlagen wurde. PDL stammt aus Pratts Interpretation von Hoares Kalkül im Formalismus der Modallogik. Eine Einführung in die Entstehung von PDL findet sich in Pratt [1980b]. Das Hoare-Tripel {A} α {B} wird durch die PDL-Formel A → [α] B erfasst, was wörtlich bedeutet, dass, wenn A wahr ist, jede erfolgreich beendete Ausführung von α mit B endet, wenn B wahr ist. Wenn diese Verbindung realisiert ist, ist es eine Routine, die Anfangsregeln von Hoares Kalkül ausschließlich unter Verwendung der Axiomatisierung von PDL zu beweisen. Dies werden wir in Abschnitt 3 ausführlich tun, der sich auf die Überlegungen zur Richtigkeit strukturierter Programme konzentriert.

Weitere Themen im Zusammenhang mit PDL sind Ergebnisse zur vergleichenden Ausdruckskraft, Entscheidbarkeit, Komplexität und Vollständigkeit einer Reihe interessanter Varianten, die durch Erweiterung oder Einschränkung von PDL auf verschiedene Weise erhalten werden. Seit seiner Einführung haben viele Varianten von PDL Aufmerksamkeit erhalten. Diese Varianten können deterministische Programme, eingeschränkte Tests, nicht reguläre Programme, Programme als Automaten, Ergänzung und Schnittmenge von Programmen, umgekehrte und unendliche Berechnungen usw. berücksichtigen. Wir werden einige davon in Abschnitt 4 vorstellen und einige Hinweise bezüglich ihrer relativen Ausdruckskraft geben. ihre Axiomatisierungen und ihre rechnerische Komplexität.

Wir schließen in Abschnitt 5.

2. Definitionen und grundlegende Ergebnisse

Wir präsentieren die Syntax und Semantik von PDL in Abschnitt 2.1. Die Beweistheorie der PDL wird in Abschnitt 2.2 mit Axiomatisierungen und Hinweisen auf die Literatur zur Vollständigkeit vorgestellt. Wir sprechen das Problem der Entscheidbarkeit und Komplexität in Abschnitt 2.3 an.

2.1 Syntax und Semantik

Propositional Dynamic Logic (PDL) dient zur Darstellung und Argumentation von Aussagenmerkmalen von Programmen. Seine Syntax basiert auf zwei Symbolsätzen: einem zählbaren Satz Φ ₀ von Atomformeln und einem zählbaren Satz Π ₀ von Atomprogrammen. Komplexe Formeln und komplexe Programme auf dieser Basis sind wie folgt definiert:

• Jede Atomformel ist eine Formel
• 0 ("falsch") ist eine Formel
• Wenn A eine Formel ist, ist ¬ A ("nicht A") eine Formel
• Wenn A und B Formeln sind, ist (A ∨ B) („A oder B“) eine Formel
• Wenn α ein Programm ist und A eine Formel ist, dann ist [α] A ("jede Ausführung von α aus dem gegenwärtigen Zustand führt zu einem Zustand, in dem A wahr ist") eine Formel
• Jedes Atomprogramm ist ein Programm
• Wenn α und β Programme sind, ist (α; β) ("mache α gefolgt von β") ein Programm
• Wenn α und β Programme sind, dann ist (α∪β) ("mache α oder β, nicht deterministisch") ein Programm,
• Wenn α ein Programm ist, dann ist α * ("α eine endliche, aber nicht deterministisch bestimmte Anzahl von Malen wiederholen") ein Programm.
• Wenn A eine Formel ist, dann ist A? ("Weiter, wenn A wahr ist, sonst fehlschlagen") ist ein Programm

Die anderen Booleschen Konnektive 1, ∧, → und ↔ werden standardmäßig als Abkürzungen verwendet. Zusätzlich kürzen wir ¬ [α] ¬ A mit A ab ("eine gewisse Ausführung von α aus dem gegenwärtigen Zustand führt zu einem Zustand, in dem A wahr ist") wie in der Modallogik. Wir schreiben α ⁿ für α;…; α mit n Vorkommen von α. Formeller:

• α ⁰ = _df 1?
• α ^{n + 1} = _df α; α ⁿ

Ebenfalls:

α ⁺ = _df α; α *

ist oft nützlich, um eine Iteration darzustellen, die unbegrenzt ist, aber mindestens einmal auftritt. Schließlich übernehmen wir die Standardregeln für das Weglassen von Klammern.

Formeln können verwendet werden, um die Eigenschaften zu beschreiben, die nach der erfolgreichen Ausführung eines Programms gelten. Zum Beispiel bedeutet die Formel [α∪β] A, dass jedes Mal, wenn das Programm α oder β erfolgreich ausgeführt wird, ein Zustand erreicht wird, in dem A gilt, während die Formel A bedeutet, dass es eine Folge alternierender Ausführungen von α und β gibt, so dass a Zustand ist erreicht, wo A gilt. Semantisch gesehen werden Formeln durch Mengen von Zuständen interpretiert, und Programme werden durch binäre Beziehungen über Zustände in einem Übergangssystem interpretiert. Genauer gesagt wird die Bedeutung von PDL-Formeln und -Programmen über Labeled Transition Systems (LTS) M = (W, R, V) interpretiert, wobei W eine nicht leere Menge von Welten oder Zuständen ist, R eine Abbildung aus der Menge Π ₀ von Atom Programme in binäre Beziehungen auf W und V ist eine Abbildung aus der Menge Φ ₀ von Atomformeln in Teilmengen von W.

Informell weist die Abbildung R jedem Atomprogramm π ∈ Π ₀ eine binäre Beziehung R (π) auf W mit der beabsichtigten Bedeutung x R (π) y zu, wenn eine Ausführung von π von x existiert, die zu y führt, während die Abbildung V. weist jeder Atomformel p ∈ ∈ ₀ eine Teilmenge V (p) von W mit der beabsichtigten Bedeutung x ∈ V (p) zu, wenn p in x wahr ist. Angesichts unserer Messwerte von 0, A, A, B, [α] A, α; β, α∪β, α * und A? Ist klar, dass R und V wie folgt induktiv erweitert werden müssen, um die beabsichtigten Bedeutungen zu liefern für die komplexen Programme und Formeln:

• x R (α; β) y, wenn es eine Welt z gibt, so dass x R (α) z und z R (β) y
• x R (α∪β) y iff x R (α) y oder x R (β) y
• x R (α *) y wenn es eine nicht negative ganze Zahl n gibt und es Welten z ₀,…, z _{n gibt,} so dass z ₀  = x, z _n  = y und für alle k = 1.. n, z _{k −1} R (α) z _k
• x R (A?) y iff x = y und y ∈ V (A)
• V (0) = ∅
• V (¬ A) = W \ V (A)
• V (A ≤ B) = V (A) ≤ V (B),
• V ([α] A) = {x: für alle Welten y, wenn x R (α) y, dann y ∈ V (A)}

Wenn x ∈ V (A) ist, dann sagen wir, dass A im Zustand x in M oder „M, x sat A“erfüllt ist.

Nennen Sie M das oben links abgebildete LTS und M 'das rechts abgebildete LTS. Formal definiert haben wir M = (W, R, V) mit W = {x ₁, x ₂ }, R (π ₁) = {(x ₁, x ₁)}, R (π ₂) = {(x ₁, x ₂)}, V (p) = {x ₁ }, V (q) = {x ₂ }, und wir haben M '= (W', R ', V') mit W '= {y ₁, y ₂, y ₃, y ₄ }, R (π ₁) = {(y ₁, y ₂), (y ₂, y ₂)}, R '(π₂) = {(y ₁, y ₃), (y ₂, y ₄)}, V '(p) = {y ₁, y ₂ }, V' (q) = {y ₃, y ₄ }. Wir haben zum Beispiel:

• M, x ₁ sat p
• M, x ₂ sat q
• M, x ₁ sat <π ₁ > p ∧ <π ₂ > q
• M, x ₁ sat [π ₁] p ∧ [π ₁ *] p
• M ', y ₁ sat <π ₁ *; π ₂ > q
• M ', y ₂ sat [π ₁ *] p
• M ', y ₁ sat [π ₁ ∪π ₂] (q ∨ p)
• M ', y ₃ sat [π ₁ ∪π ₂] 0

Betrachten Sie nun eine Formel A. Wir sagen, dass A in M gültig ist oder dass M ein Modell von A oder „M ⊨ A“ist, wenn für alle Welten x, x ∈ V (A). A gilt für alle Modelle M, M ⊨ A als gültig oder „⊨ A“. Wir sagen, dass A in M erfüllbar ist oder dass M A oder „M sat A“erfüllt, wenn es eine Welt x gibt, so dass x ∈ V (A) ist. A wird als erfüllbar oder "sat A" bezeichnet, wenn es ein Modell M gibt, so dass M sat A ist. Interessant,

saß A wenn nicht ⊨ ¬ A

⊨ A wenn nicht saß ¬ A.

Einige bemerkenswerte Formeln von PDL sind gültig. (Der Leser kann versuchen, sie formal zu beweisen, oder sich zumindest von den wenigen oben gezeigten Beispielen überzeugen.)

Α [α; β] A ↔ [α] [β] A

⊨ [α∪β] A ↔ [α] A ∧ [β] A

⊨ [α *] A ↔ A α [α] [α *] A

⊨ [A?] B ↔ (A → B)

Gleichermaßen können wir sie in ihrer doppelten Form schreiben.

⊨ A ↔ A

⊨ A ↔ A ∨ A

⊨ A ∨ A

⊨ <A?> B ↔ A ∧ B.

Ein interessanter Begriff betrifft die Informationsmenge, die mit PDL-Formeln ausgedrückt wird und in einem LTS enthalten ist. Das Verhalten eines als LTS bezeichneten Systems ist in seiner Form in der Tat oft leicht verborgen. Zum Beispiel ist es bei einfacher Inspektion leicht, sich selbst davon zu überzeugen, dass die beiden oben dargestellten LTS dasselbe Verhalten aufweisen und dieselben PDL-Formeln erfüllen. Um diesen Abschnitt über Syntax und Semantik abzuschließen, geben wir die theoretische Grundlage dieser Behauptungen.

Bei zwei LTS kann man fragen, ob sie die gleichen Formeln erfüllen. Der Begriff der Bisimulation ist zum Standardmaß für die Äquivalenz von Kripke-Modellen und markierten Übergangssystemen geworden. Eine Bisimulation zwischen den LTS M = (W, R, V) und M '= (W', R ', V') ist eine binäre Beziehung Z zwischen ihren Zuständen, so dass für alle Welten x in M und für alle Welten x ' in M ', wenn xZx' dann

• für alle Atomformeln p ∈ ∈ ₀, x ∈ V (p) iff x '∈ V' (p)
• für alle Atomprogramme π ∈ Π ₀ und für alle Welten y in M existiert, wenn x R (π) y, eine Welt y 'in M', so dass yZy 'und x' R '(π) y'
• für alle Atomprogramme π ∈ Π ₀ und für alle Welten y 'in M' existiert, wenn x 'R' (π) y ', eine Welt y in M, so dass yZy' und x R (π) y

Wir sagen, dass zwei LTS bisimilar sind, wenn zwischen ihnen eine Bisimulation besteht. Es ist seit Beginn der PDL bekannt, dass in zwei bisimilaren LTS M und M 'für alle Welten x in M und für alle Welten x' in M ', wenn xZx', dann für alle PDL-Formeln A, x ∈ V (A) iff x '∈ V' (A). Wenn also zwei LTS unter der obigen Definition der Bisimulation bisimilar sind, ist es der Fall, dass wenn xZx 'dann

• für alle Programme α und für alle Welten y in M existiert, wenn x R (α) y, eine Welt y 'in M', so dass yZy 'und x' R '(α) y'
• für alle Programme α und für alle Welten y 'in M' existiert, wenn x 'R' (α) y ', eine Welt y in M, so dass yZy' und x R (α) y

Daher kann man einfach das Verhalten von zwei LTS vergleichen, indem man nur die atomaren Programme untersucht und das Vergleichsverhalten dieser LTS auch für komplexe Programme sicher extrapoliert. Wir sagen, dass die Programmkonstrukte von PDL für die Bisimulation sicher sind. Siehe Van Benthem [1998] für genaue Charakterisierungen von Programmkonstrukten, die für die Bisimulation sicher sind.

Es ist leicht zu erkennen, dass die beiden obigen Fälle von LTS bisimilar sind. Eine Bisimulation Z zwischen M und M 'kann gegeben werden als: Z = {(x ₁, y ₁), (x ₁, y ₂), (x ₂, y ₃), (x ₂, y ₄)}. Die Zustände x ₁ und y ₁ erfüllen genau die gleichen PDL-Formeln. So auch die Zustände x ₁ und y ₂ usw.

2.2 Axiomatisierung und Vollständigkeit

Der Zweck der Beweistheorie besteht darin, die Charakterisierung der Eigenschaft ⊨ A anhand von Axiomen und Inferenzregeln bereitzustellen. In diesem Abschnitt definieren wir ein Deduzierbarkeitsprädikat ⊢ induktiv durch Operationen an Formeln, die nur von ihrer syntaktischen Struktur abhängen, so dass für alle Formeln A,

⊢ A iff ⊨ A.

Natürlich ist PDL eine Erweiterung der klassischen Aussagenlogik. Wir erwarten zunächst, dass alle Aussagen-Tautologien gelten und alle Aussagen erlaubt sind. Insbesondere modus ponens ist eine gültige Regel: aus A und A → B auf B schließen. Für jedes Programm α, das ein LTS auf die Beziehung R (α) beschränkt, erhalten wir ein Kripke-Modell, in dem die Logik der Modalität [α] die schwächste aussagekräftige normale Modallogik ist, nämlich die Logik K. Somit enthält PDL jede Instanz des bekannten Verteilungsaxiomschemas:

(A0) [α] (A → B) → ([α] A → [α] B)

und es wird unter der folgenden Inferenzregel (Notwendigkeitsregel) geschlossen:

(N) aus A schließen [α] A.

Eine modale Logik ist normal, wenn sie (A0) und (N) gehorcht. Wichtige Eigenschaften für alle α sind, dass sich [α] über die Konjunktion ∧ verteilt und die Regel der Monotonie, die es A → B erlaubt, auf [α] A → [α] B zu schließen, bewiesen werden kann. Schließlich ist PDL die am wenigsten normale Modallogik, die jede Instanz der folgenden Axiomschemata enthält

(A1) [α; β] A ↔ [α] [β] A

(A2) [α∪β] A α [α] A β [β] A

(A3) [α *] A ↔ A α [α] [α *] A

(A4) [A?] B ↔ (A → B)

und geschlossen unter der folgenden Inferenzregel (Schleifeninvarianzregel):

(I) aus A → [α] A A → [α *] A schließen

Wenn X eine Menge von Formeln ist und A eine Formel ist, dann sagen wir, dass A von X ⊢-ableitbar ist, oder „X ⊢ A“, wenn es eine Folge A ₀, A ₁,…, A _n von Formeln gibt, so dass A _n  = A und für alle i ≤ n ist A _i eine Instanz eines Axiomschemas oder einer Formel von X oder stammt aus früheren Formeln der Sequenz durch eine Inferenzregel. Ferner ist if A iff ∅ ⊢ A; in diesem Fall sagen wir, dass A ⊢-ableitbar ist. X wird als ⊢-konsistent bezeichnet, wenn nicht X ⊢ 0. Es ist leicht festzustellen, dass (I) durch das folgende Axiomschema (Induktionsaxiomschema) ersetzt werden kann:

(A5) [α *] (A → [α] A) → (A → [α *] A)

Stellen wir zunächst fest, dass (I) eine abgeleitete Regel des Beweissystems ist, die auf (A1), (A2), (A3), (A4) und (A5) basiert:

1.	A → [α] A.	Prämisse
2.	[α *] (A → [α] A)	von 1 mit (N)
3.	[α *] (A → [α] A) → (A → [α *] A)	Axiomschema (A5)
4.	A → [α *] A.	von 2 und 3 mit modus ponens

Stellen wir als nächstes fest, dass (A5) ⊢-ableitbar ist:

1.	[α *] (A → [α] A) ↔ (A → [α] A) ∧ [α] [α *] (A → [α] A)	Axiomschema (A3)
2.	A ∧ [α *] (A → [α] A) → [α] (A ∧ [α *] (A → [α] A))	von 1 unter Verwendung von Aussagen und Verteilungsmöglichkeiten von [α] über ∧
3.	A ∧ [α *] (A → [α] A) → [α *] (A ∧ [α *] (A → [α] A))	von 2 mit (I)
4.	[α *] (A → [α] A) → (A → [α *] A)	von 3 unter Verwendung von Aussagen und Verteilungsmöglichkeiten von [α *] über ∧

Die Axiomatisierung von PDL basierend auf den Axiomschemata (A1), (A2), (A3), (A4) und (A5) wurde in Segerberg [1977] vorgeschlagen. Aus den obigen Definitionen geht unmittelbar hervor, dass ⊢ in Bezug auf ⊨ richtig ist, d. H.

Wenn für alle Formeln A ⊢ A ist, dann ist ⊨ A.

Der Beweis erfolgt durch Induktion über die Länge des Abzugs von A in ⊢. Die Frage der Vollständigkeit von ⊢ in Bezug auf ⊨, dh

Wenn für alle Formeln A ⊨ A ist, dann ist ⊢ A.

wurde von mehreren Logikern verfolgt. Die in Segerberg [1977] vorgestellte Argumentation war der erste Versuch, die Vollständigkeit von ⊢ zu beweisen. Bald hatte Parikh auch einen Beweis. Als Segerberg Anfang 1978 einen Fehler in seiner Argumentation fand (den er schließlich reparierte), veröffentlichte Parikh in Parikh [1978] den ersten Beweis für die Vollständigkeit von ⊢. Seitdem wurden verschiedene Vollständigkeitsnachweise von ⊢ veröffentlicht, z. B. Kozen und Parikh [1981].

Es wurde auch nach verschiedenen alternativen Beweistheorien für PDL gesucht. Schon früh, insbesondere in Pratt [1978]. Erwähnen wir dann auch die Vollständigkeit verwandter Theorien von Nishimura [1979] und Vakarelov [1983].

Eine alternative Formulierung eines Deduzierbarkeitsprädikats für PDL erlaubt die Verwendung einer unendlichen Inferenzregel, wie zum Beispiel in Goldblatt [1992a]. (Eine unendliche Inferenzregel nimmt eine unendliche Anzahl von Prämissen an.) Sei ⊢ 'das Deduzierbarkeitsprädikat, das in der Sprache der aussagekräftigen dynamischen Logik der am wenigsten normalen Modallogik entspricht, die jede Instanz der Axiomschemata (A1), (A2) enthält. (A3) und (A4) und geschlossen nach der folgenden unendlichen Folgerungsregel:

(I ') aus {[β] [α ⁿ] A: n ≥ 0} schließen [β] [α *] A.

Es kann bewiesen werden, dass ⊢ 'sowohl gesund als auch vollständig in Bezug auf ⊨ ist, dh

Für alle Formeln A gilt if 'A iff ⊨ A.

Mit anderen Worten, was die Erzeugung der Menge aller gültigen Formeln betrifft, sind die Beweissysteme ⊢ und ⊢ 'äquivalent.

2.3 Entscheidbarkeit und Komplexität

Ziel der Komplexitätstheorie ist es, die Berechenbarkeit der Eigenschaft sat A in Bezug auf zeitliche oder räumliche Ressourcen zu ermitteln. Die Komplexität einer Logik L wird häufig mit dem Problem der Entscheidung über die Erfüllbarkeit ihrer Formeln identifiziert, definiert als:

(L-SAT) Ist A bei einer Formel A von L erfüllbar?

In diesem Abschnitt untersuchen wir die Komplexität des folgenden Entscheidungsproblems:

(PDL-SAT) Ist A bei einer Formel A von PDL erfüllbar?

Die vollständige Axiomatisierung von PDL ist eine rekursive Definition des Satzes gültiger PDL-Formeln oder mit anderen Worten des Satzes von Formeln, deren Negation nicht erfüllbar ist. In Bezug auf das Problem (PDL-SAT) haben wir daher eine Unterprozedur, die mit „Nein“antworten würde, wenn die PDL-Formel A nicht erfüllbar wäre. Die Unterprozedur (SP1) besteht darin, alle Formeln ⊢-ableitbar aufzulisten, ausgehend von den Axiomen und mit Hilfe der Inferenzregeln auf andere Theoreme zu schließen. Wenn genügend Zeit zur Verfügung steht und eine Formel ⊢-ableitbar ist, würde die Unterprozedur sie schließlich finden. Wenn also A nicht erfüllbar ist, muss (SP1) schließlich ¬ A finden und dabei mit „Nein“antworten.

Wenn jedoch die Formel A erfüllt werden kann, würde (SP1) niemals ¬ A finden. Es würde für immer laufen, und man konnte sich zu keinem Zeitpunkt sicher sein. Aber es gibt einen Ausweg aus dieser Unsicherheit. Wir können uns auch eine zweite Unterprozedur vorstellen, die mit „Ja“antwortet, wenn eine PDL-Formel erfüllt werden kann. In der Tat war eines der frühesten Ergebnisse bei PDL der Beweis, dass PDL die endliche Modelleigenschaft besitzt, d. H.

Für alle Formeln A existiert, wenn sat A, ein endliches Modell M, so dass M sat A ist.

Die Eigenschaft des endlichen Modells bietet eine Grundlage für eine Unterprozedur (SP2), die darin besteht, die endlichen Modelle der PDL einzeln aufzulisten und zu testen, ob eines von ihnen die Formel erfüllt. (Für alle Formeln A und für alle endlichen Modelle M ist es einfach zu testen, ob M sat A ist, indem die Definition von V (A) angewendet wird.) Wenn A also erfüllbar ist, muss es schließlich ein Modell M finden, so dass M sat A, und antworten Sie mit "Ja", wenn dies der Fall ist. Symmetrisch zur ersten Unterprozedur (SP1), wenn die Formel A nicht erfüllbar ist, wird (SP2) niemals ein Modell finden, das sie erfüllt, es wird für immer laufen und man kann sich zu keinem Zeitpunkt sicher sein.

Wenn wir nun (SP1) und (SP2) miteinander kombinieren, können wir entscheiden, ob eine PDL-Formel A erfüllt werden kann. Es reicht aus, sie parallel auszuführen: Wenn A erfüllt ist, antwortet (SP2) schließlich mit "Ja", wenn A nicht erfüllt ist, antwortet (SP1) schließlich mit "Nein". Die Prozedur wird angehalten, wenn entweder (SP1) oder (SP2) eine Antwort liefert.

Wenn das erhaltene Verfahren ausreicht, um zu dem Schluss zu kommen, dass das Problem (PDL-SAT) entscheidbar ist, ist es in der Praxis sehr unwirksam. Es gibt ein Ergebnis - aufgrund von Fischer und Ladner [1979] und Kozen und Parikh [1981] - stärker als die endliche Modelleigenschaft, dh die kleine Modelleigenschaft:

Für alle Formeln A existiert, wenn sat A, ein endliches Modell M mit einer exponentiellen Größe in A, so dass M sat A ist.

Dies bedeutet, dass wir jetzt wissen würden, wann wir aufhören müssen, nach einem Modell zu suchen, das eine Formel in der Prozedur (SP2) erfüllt. Daher können wir (SP2) verwenden, um zu testen, ob eine Formel erfüllt werden kann. Wenn wir jedoch alle kleinen Modelle erschöpft haben, können wir den Schluss ziehen, dass die Formel nicht erfüllt werden kann. Dies ergibt eine Prozedur, die nicht deterministisch in exponentieller Zeit (NEXPTIME) abläuft: Erraten Sie ein Größenmodell, das höchstens einfach exponentiell ist, und prüfen Sie, ob es die Formel erfüllt. Die wichtigsten Ergebnisse in der Komplexitätstheorie der PDL stammen jedoch von Fischer und Ladner [1979] und Pratt [1980a]. Fischer und Ladner [1979] beobachteten zunächst, dass eine PDL-Formel die Berechnung einer linearen raumgebundenen alternierenden Turing-Maschine effizient beschreiben kann, und stellten zunächst die Untergrenze der Exponentialzeit von (PDL-SAT) fest. Die EXPTIME-Obergrenze von (PDL-SAT) wurde von Pratt [1980a] erhalten,wer verwendete das Äquivalent für PDL der Methode der Tableaus. Somit ist (PDL-SAT) EXPTIME-vollständig. (Ein Algorithmus, der in der Praxis effizienter ist, obwohl er im schlimmsten Fall immer noch in deterministischer Exponentialzeit läuft, wird in De Giacomo und Massacci [2000] vorgeschlagen.)

3. Strukturierte Programmierung und Richtigkeit der Programme

Historisch gesehen stammt die Logik von Programmen aus der Arbeit von Informatikern in den späten 1960er Jahren, die daran interessiert waren, Programmiersprachen Bedeutung zuzuweisen und einen strengen Standard für Beweise für die Programme zu finden. Beispielsweise können solche Beweise die Richtigkeit eines Programms in Bezug auf ein erwartetes Verhalten oder die Beendigung eines Programms betreffen. Eine wegweisende Arbeit ist Floyd [1967], die eine Analyse der Eigenschaften strukturierter Computerprogramme unter Verwendung von Flussdiagrammen präsentiert. Einige frühe Arbeiten wie Yanov [1959] oder Engeler [1967] hatten formale Sprachen weiterentwickelt und studiert, in denen die Eigenschaften von Programmverbindungen ausgedrückt werden können. Der Formalismus von Hoare [1969] war ein Meilenstein im Aufkommen von PDL. Es wurde als strenge axiomatische Interpretation von Floyds Flussdiagrammen vorgeschlagen. Wir sprechen oft über Hoare-Logik oder Floyd-Hoare-Logik.oder Hoare-Kalkül, wenn auf diesen Formalismus Bezug genommen wird. Der Hoare-Kalkül befasst sich mit der Wahrheit von Aussagen („Hoare-Tripel“) wie {A} α {B}, die eine Verbindung zwischen einer Vorbedingung A, einem Programm α und einer Nachbedingung B herstellen. Es zeigt an, dass immer dann, wenn A als Voraussetzung für die Ausführung von α gilt, B nach der erfolgreichen Ausführung von α als Nachbedingung gilt.

Dies war vor einigen Jahrzehnten der Fall, und es ist immer noch der Fall: Die Validierung eines Programms erfolgt häufig durch Testen an einer angemessenen Anzahl von Eingaben. Wenn eine Eingabe nicht die erwartete Ausgabe liefert, ist der „Fehler“behoben. Wenn wir schließlich für jede getestete Eingabe die erwartete Ausgabe erhalten, ist man der Ansicht, dass das Programm keinen Fehler aufweist. Dies ist jedoch eine zeitaufwändige Validierungsmethode und lässt Platz für nicht getestete Eingaben, die fehlschlagen würden. Das Auffinden dieser Fehler nach der Implementierung und Inbetriebnahme des Programms ist noch ressourcenintensiver. Das Nachdenken über die Programmkorrektheit mit formalen Methoden ist für kritische Systeme von entscheidender Bedeutung, da es eine Möglichkeit bietet, umfassend zu beweisen, dass ein Programm keine Fehler aufweist.

3.1 Hoare-Kalkül

Um die Art der Prinzipien von Programmen zu veranschaulichen, die von den Regeln im Hoare-Kalkül erfasst werden, reicht es aus, einige von ihnen zu konsultieren. (NB: Die Regeln bedeuten, dass, wenn alle Aussagen über der Regelzeile die Prämissen enthalten, dann auch die Aussage unter der Regelzeile die Schlussfolgerung enthält.)

{A} α 1 {B} {B} α 2 {C}	(Kompositionsregel)
{A} α 1; α 2 {C}

Die Kompositionsregel erfasst die elementare sequentielle Komposition von Programmen. Als Prämissen haben wir zwei Annahmen über die teilweise Korrektheit zweier Programme α ₁ und α ₂. Die erste Annahme ist, dass wenn α ₁ in einem Zustand ausgeführt wird, der A erfüllt, es in einem Zustand endet, der B erfüllt, wann immer es anhält. Die zweite Annahme ist, dass wenn α ₂ in einem Zustand ausgeführt wird, der B erfüllt, es in einem Zustand endet, der C erfüllt, wann immer es anhält. Die Schlussfolgerung der Regel betrifft die teilweise Korrektheit des Programms α ₁; α ₂ (dh α _{1, das} nacheinander aus α _{2 zusammengesetzt ist}), das sich aus den beiden Annahmen ergibt. Wir können nämlich schließen, dass, wenn α ₁; α ₂ in einem Zustand ausgeführt wird, der A erfüllt, es in einem Zustand endet, der C erfüllt, wann immer es anhält.

Die Iterationsregel ist wichtig, da sie die wesentliche Fähigkeit von Programmen erfasst, einen Teil des Codes wiederholt auszuführen, bis eine bestimmte Bedingung nicht mehr gilt.

{A ∧ B} α {A}	(Iterationsregel)
{A} während B α {¬ B ∧ A} tut

Schließlich sind die beiden Konsequenzregeln von grundlegender Bedeutung, um eine formale Grundlage für intuitiv klares Denken zu schaffen, das schwächere Nachbedingungen bzw. stärkere Voraussetzungen beinhaltet.

{A} α {B} B → C.	(Konsequenzregel 1)
{A} α {C}

C → A {A} α {B}	(Regel der Konsequenz 2)
{C} α {B}

Aus dem in Hoare [1969] vorgestellten Formalismus lassen wir seine Axiomschemata weg, da er eine Sprache erster Ordnung erfordern würde. Schließlich werden in späteren Arbeiten zur Hoare-Logik häufig weitere Regeln hinzugefügt. Siehe Apt [1979] für einen frühen Überblick.

3.2 Hoare-Kalkül und PDL

Dynamische Logik ergibt sich aus Pratts Interpretation von Hoare-Tripeln und Hoare-Kalkül im Formalismus der Modallogik. Mit der Modalität [α] können wir formal ausdrücken, dass alle durch Ausführen von α erreichbaren Zustände die Formel A erfüllen. Dies erfolgt durch Schreiben von [α] A. Somit wird das Hoare-Tripel {A} α {B} einfach durch die PDL-Formel erfasst

A → [α] B.

Darüber hinaus lassen sich wichtige Programmierkonstrukte durch definitive Abkürzung leicht in PDL einführen:

• wenn A dann α sonst β = _df ((A ?; α) ∪ (¬ A ?; β))
• während A do α = _df ((A ?; α) *; ¬ A?)
• wiederhole α bis A = _df (α; ((¬ A; α) *; A?))
• abort = _df 0?
• überspringen = _df 1?

Es scheint also, dass wir mit PDL gut gerüstet sind, um die Richtigkeit strukturierter Programme logisch zu beweisen. Abgesehen von dieser eher handwinkenden Verbindung zwischen PDL und Hoare-Kalkül ist vielleicht noch nicht klar, wie sie sich formal verhalten. PDL ist in der Tat eine Verallgemeinerung der Hoare-Rechnung in dem Sinne, dass alle Regeln der Hoare-Rechnung im axiomatischen System der PDL bewiesen werden können. (Streng genommen enthält der Hoare-Kalkül Axiome, die die erweiterte Sprache der dynamischen Logik erster Ordnung erfordern würden.) Dies ist ziemlich bemerkenswert, daher werden wir hier die beiden obigen Regeln als Beispiele zeigen.

Die Beweise beginnen mit der Annahme der Prämissen der Regeln. Unter Verwendung dieser Annahmen, Axiome und Regeln der PDL und nichts anderem besteht das Ziel darin, festzustellen, dass die Schlussfolgerung der Regeln logisch folgt. Daher beginnen wir für die Regel der Zusammensetzung mit der Annahme von {A} α ₁ {B}, dh A → [α ₁] B in seiner PDL-Formulierung, und mit der Annahme von {B} α ₂ {C}, dh B. → [α ₂] C. Das Ziel ist es zu beweisen, dass {A} α ₁; α ₂ {C}. Genau wollen wir feststellen, dass A → [α ₁; α ₂] C aus der Menge der Formeln {A → [α ₁] B, B → [α ₂] C} ⊢-ableitbar ist.

1.	A → [α 1] B.	Annahme {A} α 1 {B}
2.	B → [α 2] C.	Annahme {B} α 2 {C}
3.	[α 1] B → [α 1] [α 2] C.	Aus 2 unter Verwendung der Monotonie von [α 1]
4.	A → [α 1] [α 2] C.	von 1 und 3 unter Verwendung von Aussagen
5.	[α 1; α 2] C ↔ [α 1] [α 2] C.	Axiomschema (A1)
6.	A → [α 1; α 2] C.	von 4 und 5 unter Verwendung von Aussagen
- -	{A} α 1; α 2 {C}

Der Beweis der Iterationsregel ist etwas komplizierter.

1.	A ∧ B → [α] A.	Annahme {A ∧ B} α {A}
2.	A → (B → [α] A)	von 1 unter Verwendung von Aussagen
3.	[B?] [Α] A ↔ (B → [α] A)	Axiomschema (A4)
4.	A → [B?] [Α] A.	von 2 und 3 unter Verwendung von Aussagen
5.	[B?;; α] A ↔ [B?] [α] A.	Axiomschema (A1)
6.	A → [B ?; α] A.	von 4 und 5 unter Verwendung von Aussagen
7.	A → [(B ?; α) *] A.	ab 6 mit (I)
8.	A → (¬ B → (¬ B ∧ A))	Satztautologie
9.	A → [(B ?; α) *] (¬ B → (¬ B ∧ A))	von 7 und 8 unter Verwendung der Monotonie von [(B ?; α) *] und der Argumentation
10.	[¬ B?] (¬ B ∧ A) ↔ (¬ B → (¬ B ∧ A))	Axiomschema (A4)
11.	A → [(B ?; α) *] [¬ B?] (¬ B ∧ A)	von 9 und 10 unter Verwendung der Monotonie von [(B ?; α) *] und der Argumentation
12.	[(B ?; α) *; ¬ B?] (¬ B ∧ A) ↔ [(B ?; α) *] [¬ B?] (¬ B ∧ A)	Axiomschema (A1)
13.	A → [(B ?; α) *; ¬ B?] (¬ B ∧ A)	von 12 unter Verwendung von Aussagen
- -	{A} während B α {¬ B ∧ A} tut

Im Zusammenhang mit PDL sind die beiden Konsequenzregeln tatsächlich Sonderfälle der Kompositionsregel. Um die erste Regel zu erhalten, ersetzen Sie α ₁ durch α und α ₂ durch Überspringen. Um die zweite Regel zu erhalten, ersetzen Sie α ₁ durch Überspringen und α ₂ durch α. Es genügt, das Axiomschema (A4) anzuwenden und zu bemerken, dass [α; überspringen] A ↔ [α] A und [α; überspringen] A ↔ [α] A sind auch für alle A und alle α ⊢-ableitbar.

3.3 Völlige Richtigkeit

Nach Hoares eigenem Eingeständnis in Hoare [1979] war sein ursprünglicher Kalkül lediglich ein Ausgangspunkt und litt unter einigen Einschränkungen. Insbesondere erlaubt es nur, über teilweise Korrektheit nachzudenken. Das heißt, die Wahrheit einer Aussage {A} α {B} stellt nur sicher, dass alle Ausführungen von α, die in einem Zustand beginnen, der A erfüllt, in einem Zustand enden, der B erfüllt, oder nicht anhalten. Das heißt, ein teilweise korrektes Programm kann nicht terminierende Ausführungen haben. (Tatsächlich ist ein Programm ohne beendende Ausführung immer teilweise korrekt. Dies ist beispielsweise beim Programm der Fall, wenn 1 überspringt. Die Formel A → [ während 1 überspringt] B ist für alle Formeln A und B ableitbar.) Der Kalkül bietet keine Grundlage für den Nachweis, dass ein Programm beendet wird. Sie kann geändert werden, um die vollständige Korrektheit der Programme zu berücksichtigen: teilweise Korrektheit plus Beendigung. Dies wird durch Änderung der Iterationsregel erreicht. Wir präsentieren es hier nicht und verweisen den interessierten Leser auf Apt [1981].

Lassen Sie uns zunächst beobachten, dass man für deterministische Programme bereits die totale Korrektheit über solche Formeln erfassen kann

A → B.

Der Ausdruck B bedeutet, dass es eine Ausführung von α gibt, die in einem Zustand endet, der B erfüllt. Wenn α deterministisch ist, ist diese mögliche Beendigung der Ausführung die eindeutige Ausführung von α. Wenn man also zuerst beweisen kann, dass ein Programm deterministisch ist, funktioniert dieser Trick gut genug, um seine vollständige Richtigkeit zu beweisen.

Im Bereich der PDL gibt es eine allgemeine Lösung für das Problem der vollständigen Korrektheit. Aber wir müssen es ein wenig erweitern. Pratt hatte bereits in Pratt [1980b] angedeutet, dass PDL nicht ausdrucksstark genug ist, um die Endlosschleife von Programmen zu erfassen. Als Reaktion darauf wurde von Streett [1982] PDL mit Wiederholung (RPDL) eingeführt. Es enthält für alle Programme α den Ausdruck Δα, der für einen neuen Satz mit Semantik steht

V (Δα) = {x: Es gibt eine unendliche Folge x ₀, x ₁, … von Zuständen, so dass x ₀  = x und für alle n ≥ 0 x _n R (α) x _{n + 1} }

Streett [1982] vermutete, dass RPDL axiomatisiert werden kann, indem dem Beweissystem von PDL genau die folgenden Axiomschemata hinzugefügt werden.

(A6) Δα → Δα

(A7) [α *] (A → A) → (A → Δα)

Der Beweis der Vermutung wurde in Sakalauskaite und Valiev [1990] erbracht. (Eine Version der Vermutung in der Variante der kombinatorischen PDL wurde auch in Gargov und Passy [1988] bewiesen.)

Es ist leicht zu erkennen, dass in dem oben dargestellten Hoare-Kalkül eine Nichtbeendigung nur aus der Iterationsregel resultieren kann. Analog kann die Nichtbeendigung eines PDL-Programms nur durch die Verwendung der unbegrenzten Iteration erfolgen. Der Ausdruck Δα zeigt an, dass α * divergieren kann, und dies ist genau die Art von Begriff, die wir brauchen. Wir können nun induktiv ein Prädikat ∞ definieren, so dass für ein Programm α die Formel ∞ (α) genau dann wahr ist, wenn α in eine nicht terminierende Berechnung eintreten kann.

∞ (π): = 0 wobei π ∈ Π ₀

∞ (φ?): = 0

∞ (α ∪ β): = ∞ (α) ∨ (β)

∞ (α; β): = ∞ (α) ∨ ∞ (β)

∞ (α *): = Δα ∨ ∞ (α)

Schließlich kann die vollständige Richtigkeit eines Programms durch Formeln dieser Art ausgedrückt werden

A → (¬∞ (α) ∧ [α] B)

was wörtlich bedeutet, dass wenn A der Fall ist, das Programm α nicht für immer ausgeführt werden kann und jede erfolgreiche Ausführung in einem Zustand endet, der B erfüllt.

4. Einige Varianten

Ergebnisse bezüglich der vergleichenden Ausdruckskraft, Entscheidbarkeit, Komplexität, Axiomatisierung und Vollständigkeit einer Reihe von PDL-Varianten, die durch Erweiterung oder Einschränkung ihrer Syntax und Semantik erhalten wurden, sind Gegenstand einer Fülle von Literatur. Wir können nur so viel sagen und werden nur einige dieser Varianten ansprechen, wobei große Teile der ansonsten wichtigen Arbeit in der dynamischen Logik weggelassen werden.

4.1 PDL ohne Tests

Das Axiomschema [A?] B ↔ (A → B) scheint anzuzeigen, dass für jede Formel C eine äquivalente testfreie Formel C 'existiert - dh es gibt eine testfreie Formel C', so dass ⊨ C ↔ C '. Es ist interessant zu beobachten, dass diese Behauptung falsch ist. PDL ₀ sei die Beschränkung von PDL auf testfreie reguläre Programme, dh Programme, die keine Tests enthalten. Berman und Paterson [1981] betrachteten die PDL-Formel <(p ?; π) *; ¬ p ?; π; p?> 1, was ist

< while p do π> p

und bewiesen, dass es keine PDL ₀ -Formel gibt, die dieser äquivalent ist. Daher hat PDL mehr Ausdruckskraft als PDL ₀. Ihr Argument kann tatsächlich wie folgt verallgemeinert werden. Für alle n ≥ 0 sei PDL _{n + 1} die Teilmenge der PDL, in der Programme Tests A enthalten können. nur wenn A eine PDL _n Formel ist. Für alle n ≥ 0 betrachteten Berman und Paterson die PDL _{n + 1-} Formel A _{n + 1,} definiert durch

< Während A _n tun π _n > <π _n > A _n

wobei A ₀  = p und π ₀  = π und bewiesen hat, dass es für alle n ≥ 0 keine PDL _n -Formel gibt, die A _{n + 1 entspricht}. Daher hat PDL _{n +} 1 für alle n ≥ 0 eine stärkere Ausdruckskraft als PDL _n.

4.2 PDL mit Umkehrung

CPDL ist die Erweiterung von PDL mit Converse. Es ist ein Konstrukt, das seit Beginn der PDL berücksichtigt wurde. Für alle Programme α sei α ^-1 für ein neues Programm mit Semantik

x R (α ^-1) y iff y R (α) x.

Das umgekehrte Konstrukt ermöglicht es uns, Fakten über Zustände auszudrücken, die dem aktuellen vorausgehen, und über Programme rückwärts zu argumentieren. Zum Beispiel bedeutet [α ^-1] A, dass A vor der Ausführung von α halten musste. Wir haben

→ A → [α] <α ^-1 > A, ⊨ A → [α ^-1] A.

Das Hinzufügen des umgekehrten Konstrukts ändert die Eigenschaften von PDL in keiner signifikanten Weise. Durch Hinzufügen jeder Instanz der folgenden Axiomschemata:

(A8) A → [α] <α ^-1 > A

(A9) A → [α ^-1] A

Für das Proof-System von PDL erhalten wir ein solides Prädikat für die vollständige Ableitbarkeit in der erweiterten Sprache. Siehe Parikh [1978] für Details. CPDL hat die Eigenschaft Small Model und (CPDL-SAT) ist EXPTIME-vollständig.

Es ist leicht zu bemerken, dass CPDL mehr Ausdruckskraft als PDL hat. Betrachten Sie dazu die CPDL-Formel <π ^-1 > 1 und die LTSs M = (W, R, V) und M '= (W', R ', V'), wobei W = {x, y}, R. (π) = {(x, y)}, W '= {y'}, R '(π) = ∅ und V (x) = V (y) = V' (y ') = ∅. Da M, y saß <π ^-1 > 1, nicht M ', y' saß <π ^-1 > 1, und weil für alle PDL-Formeln A der Fall ist, dass M, y saß A, wenn M ', y' saß A, dann ist klar, dass keine PDL-Formel <π ^-1 > 1 entspricht.

4.3 PDL mit Wiederholung und Schleife

Wir haben bereits in Abschnitt 3.3 die Möglichkeit der Wiederholung durch die Einführung von RPDL aufgezeigt. Hier fassen wir weitere Ergebnisse über RPDL und seinen Zusammenhang mit anderen Variationen des Begriffs der Wiederholung von Programmen zusammen.

In Bezug auf die Komplexitätstheorie von RPDL hatte Streett [1982] bereits festgestellt, dass RPDL die endliche Modelleigenschaft besitzt; genau, dass jede RPDL-erfüllbare Formel A in einem Modell mit einer Größe erfüllt ist, die höchstens dreifach exponentiell in der Länge von A ist. Ein automatentheoretisches Argument, das den Schluss zulässt, dass das Problem (RPDL-SAT) in deterministischer dreifacher Exponentialzeit (3-EXPTIME) gelöst werden kann. Die Lücke zwischen dieser Obergrenze für die Entscheidung (RPDL-SAT) und der einfachen Exponentialzeit-Untergrenze für die Entscheidung (PDL-SAT) war somit offen. Das Problem war stark mit dem wachsenden Interesse der Informatiker verbunden, die Komplexität der zeitlichen Logik und insbesondere des (propositionalen) modalen μ-Kalküls (MMC) aufgrund von Kozen [1983] zu bestimmen, da RPDL einen linearen Schlag hat. Übersetzung in MMC. Außerdem,Streetts Argumentation hat einen Präzedenzfall für die mittlerweile allgegenwärtige Verwendung von Automatentechniken zum Nachweis der rechnerischen Eigenschaften von Programmlogiken und zeitlichen Logiken geschaffen. In Vardi und Stockmeyer [1985] wurde eine Obergrenze in der nicht deterministischen Exponentialzeit gezeigt. In Emerson und Jutla [1988] und in seiner endgültigen Form in Emerson und Jutla [1999] wurde gezeigt, dass (MMC-SAT) und (RPDL-SAT) EXPTIME-vollständig sind. Wenn wir den umgekehrten Operator von Abschnitt 4.2 hinzufügen, erhält man CRPDL. Die Komplexität von (CRPDL-SAT) blieb einige Jahre offen, aber es kann auch gezeigt werden, dass sie EXPTIM ist. Dies wird erreicht, indem die Techniken von Emerson und Jutla [1988] und Vardi [1985] wie in Vardi [1998] kombiniert werden. In Vardi und Stockmeyer [1985] wurde eine Obergrenze in der nicht deterministischen Exponentialzeit gezeigt. In Emerson und Jutla [1988] und in seiner endgültigen Form in Emerson und Jutla [1999] wurde gezeigt, dass (MMC-SAT) und (RPDL-SAT) EXPTIME-vollständig sind. Wenn wir den umgekehrten Operator von Abschnitt 4.2 hinzufügen, erhält man CRPDL. Die Komplexität von (CRPDL-SAT) blieb einige Jahre offen, aber es kann auch gezeigt werden, dass sie EXPTIM ist. Dies wird erreicht, indem die Techniken von Emerson und Jutla [1988] und Vardi [1985] wie in Vardi [1998] kombiniert werden. In Vardi und Stockmeyer [1985] wurde eine Obergrenze in der nicht deterministischen Exponentialzeit gezeigt. In Emerson und Jutla [1988] und in seiner endgültigen Form in Emerson und Jutla [1999] wurde gezeigt, dass (MMC-SAT) und (RPDL-SAT) EXPTIME-vollständig sind. Wenn wir den umgekehrten Operator von Abschnitt 4.2 hinzufügen, erhält man CRPDL. Die Komplexität von (CRPDL-SAT) blieb einige Jahre offen, es kann jedoch auch gezeigt werden, dass sie EXPTIM ist. Dies wird erreicht, indem die Techniken von Emerson und Jutla [1988] und Vardi [1985] wie in Vardi [1998] kombiniert werden. Die Komplexität von (CRPDL-SAT) blieb einige Jahre offen, es kann jedoch auch gezeigt werden, dass sie EXPTIM ist. Dies wird erreicht, indem die Techniken von Emerson und Jutla [1988] und Vardi [1985] wie in Vardi [1998] kombiniert werden. Die Komplexität von (CRPDL-SAT) blieb einige Jahre offen, aber es kann auch gezeigt werden, dass sie EXPTIM ist. Dies wird erreicht, indem die Techniken von Emerson und Jutla [1988] und Vardi [1985] wie in Vardi [1998] kombiniert werden.

In Abschnitt 3.3 haben wir ein Prädikat ∞ definiert, wobei ∞ (α) bedeutet, dass α eine nicht terminierende Berechnung haben kann. Wir nennen LPDL die Logik, die durch Erweitern von PDL mit dem Prädikat ∞ erhalten wird. RPDL ist eindeutig mindestens so ausdrucksstark wie LPDL. Die induktive Definition von ∞ (α) in der Sprache der RPDL ist ein Beweis dafür. RPDL ist in der Tat streng ausdrucksstärker als LPDL. Dies wurde in Harel und Sherman [1982] gezeigt. Wie zu vermuten ist, haben sowohl RPDL als auch LPDL eine stärkere Ausdruckskraft als PDL. Es wird durch den Nachweis festgestellt, dass einige Formeln von RPDL und LPDL keine äquivalente Expression in PDL aufweisen. Der Beweis beinhaltet die Filtrationstechnik, die darauf ausgelegt ist, ein LTS zu einem endlichen Modell zusammenzufassen, während die Wahrheit oder Falschheit bestimmter Formeln unverändert bleibt. Für einen Satz von PDL-Formeln X,Es besteht darin, die Zustände eines LTS, die genau die gleichen Formeln in X erfüllen, in Äquivalenzklassen zu gruppieren. Die so erhaltene Menge von Äquivalenzklassen von Zuständen wird zur Menge von Zuständen des Filtratmodells, und ein Übergang wird entsprechend über ihnen aufgebaut.

Mit einem sorgfältig ausgewählten Satz FL (A), der von einer PDL-Formel A abhängt (dem sogenannten Fischer-Ladner-Verschluss des Satzes von Unterformeln von A), ergibt eine Filtration eines LTS M ein endliches Filtrat M ', wie z dass A in einer Welt u in M genau dann erfüllbar ist, wenn es in der Äquivalenzklasse erfüllt ist, die u im Filtrat enthält. (Siehe Fischer und Ladner [1979].)

Wir können nun die Filtrationen des LTS M = (W, R, V) betrachten, wobei

• W = {(i, j): j und i positive ganze Zahlen, 0 ≤ j ≤ i} ∪ {u}
• (i, j) R (π) (i, j -1), wenn 1 ≤ j ≤ i
• u R (π) (i, i) für jedes i
• V (p) = ∅ für jedes p ∈ ∈ ₀

In einem Satz geht es in M darum, dass es aus der Welt u unendlich viele endliche π-Pfade mit wachsender Länge gibt. Wir haben sowohl M, u sat ¬Δπ als auch M, u sat ¬∞ (π *). Für jede PDL-Formel A haben wir jedoch sowohl Δπ als auch ∞ (π *), die bei der Äquivalenzklasse von u in dem Modell erfüllt sind, das durch Filtration von M mit FL (A) erhalten wird. In der Tat muss die Filtration einige Zustände von M kollabieren und einige Schleifen erzeugen. Somit gibt es keine PDL-Formel, die entweder Δπ oder ∞ (π *) ausdrücken kann. und doch werden wir sowohl Δπ als auch ∞ (π *) haben, die bei der Äquivalenzklasse von u in jedem endlichen Filtrat von M erfüllt sind. Somit können weder Δπ noch ∞ (π *) in PDL ausgedrückt werden.

Es gibt andere Möglichkeiten, die Behauptung zu ermöglichen, dass ein Programm für immer ausgeführt werden kann. Zum Beispiel schlug Danecki [1984a] eine Prädikat- Schaluppe vor, um Programme zu qualifizieren, die in starke Schleifen eintreten können, dh:

V (Schaluppe (α)) = {x: x R (α) x}

Nennen wir SLPDL die Logik, die durch Erweitern von PDL mit Sloop (α) erhalten wird. RPDL und SLPDL sind im Wesentlichen unvergleichbar: Das Prädikat Δ ist in SLPDL nicht definierbar, und das Prädikat Sloop ist in RPDL nicht definierbar. SLPDL besitzt nicht die Eigenschaft des endlichen Modells. Zum Beispiel die Formel

[π *] (1 ∧ ¬ Schaluppe (π ⁺))

ist nur in unendlichen LTSs erfüllbar. Dennoch stellte Danecki [1984a] die Entscheidbarkeit von (SLPDL-SAT) -Formeln in deterministischer Exponentialzeit fest.

4.4 PDL mit Schnittpunkt

Ein anderes Konstrukt wurde untersucht: die Überschneidung von Programmen. Durch Hinzufügen der Schnittmenge von Programmen zur PDL erhalten wir die logische IPDL. In IPDL steht für alle Programme α, β der Ausdruck α∩β für ein neues Programm mit Semantik

x R (α∩β) y iff x R (α) y und x R (β) y

Zum Beispiel ist das beabsichtigte Lesen von A, dass, wenn wir α und β im gegenwärtigen Zustand ausführen, ein Zustand existiert, der von beiden Programmen erreichbar ist, der A erfüllt. Als Ergebnis haben wir

⊨ A → A ∧ A.

aber im Allgemeinen haben wir

nicht ⊨ A ∧ A → A.

Obwohl die Überschneidung von Programmen bei verschiedenen Anwendungen von PDL auf künstliche Intelligenz und Informatik eine wichtige Rolle spielt, blieben die Beweistheorie und die Komplexitätstheorie von PDL mit Überschneidung mehrere Jahre lang unerforscht. In Bezug auf die Komplexitätstheorie von IPDL treten Schwierigkeiten auf, wenn man die Eigenschaft des endlichen Modells betrachtet. In der Tat das Konstrukt Korvette kann (α) in IPDL ausgedrückt werden. In der aussagekräftigen dynamischen Logik mit Schnittmenge ist sie äquivalent zu 1. Wir können also die IPDL-Formel von Abschnitt 4.3 anpassen, und das haben wir

[π *] (1 ∧ [π ⁺ ∩1?] 0)

ist nur in unendlichen LTSs erfüllbar. Mit anderen Worten, IPDL besitzt nicht die Eigenschaft des endlichen Modells. Danecki [1984b] untersuchte die Komplexitätstheorie von IPDL und zeigte, dass die Entscheidung (IPDL-SAT) in deterministischer doppelter Exponentialzeit erfolgen kann. (Ein moderner Beweis wird in Göller, Lohrey und Lutz [2007] vorgestellt.) Die Komplexitätslücke zwischen dieser doppelten Exponentialzeit-Obergrenze für die Entscheidung (IPDL-SAT) und der einfachen Exponentialzeit-Untergrenze für die Entscheidung (PDL-SAT) erhalten von Fischer und Ladner [1979] blieb mehr als zwanzig Jahre offen. Im Jahr 2004 stellte Lange [2005] die Untergrenze des Exponentialraums von (IPDL-SAT) fest. In 2006,Lange und Lutz [2005] gaben einen Beweis für eine doppelte Exponentialzeit-Untergrenze des Erfüllbarkeitsproblems für IPDL ohne Tests durch eine Reduktion des Wortproblems exponentiell raumgebundener alternierender Turing-Maschinen. Bei dieser Reduktion ist die Rolle des Iterationskonstrukts wesentlich, da laut Massacci [2001] das Erfüllbarkeitsproblem für iterationsfreie IPDL ohne Tests nur PSPACE-vollständig ist. Durch Hinzufügen des umgekehrten Konstrukts zu IPDL erhalten wir ICPDL. Das Erfüllbarkeitsproblem von ICPDL wurde von Göller, Lohrey und Lutz [2007] als 2-EXPTIME-vollständig erwiesen. Das Erfüllbarkeitsproblem von ICPDL wurde von Göller, Lohrey und Lutz [2007] als 2-EXPTIME-vollständig erwiesen. Das Erfüllbarkeitsproblem von ICPDL wurde von Göller, Lohrey und Lutz [2007] als 2-EXPTIME-vollständig erwiesen.

In Bezug auf die Beweistheorie von IPDL treten Schwierigkeiten auf, wenn wir erkennen, dass kein Axiomschema in der Sprache von PDL mit Schnittmenge der Semantik x R (α∩β) y iff x R (α) y und x R (entspricht) β) y des Programms α∩β. Das heißt, nicht in der gleichen Weise, dass beispielsweise die Axiomschemata (A1) und (A2) der Semantik der Programme α; β und α∪β "entsprechen". Aus diesem Grund war die Axiomatisierung von PDL mit Schnittpunkt offen, bis das vollständige Beweissystem in Balbiani und Vakarelov [2003] entwickelt wurde.

In einer anderen Variante von PDL wird aufgrund von Peleg [1987] und weiter untersucht von Goldblatt [1992b] der Ausdruck α∩β als "do α und β parallel" interpretiert. In diesem Zusammenhang sind die binären Beziehungen R (α) und R (β) keine Sätze von Paaren der Form (x, y) mit x, y Welten mehr, sondern Sätze von Paaren der Form (x, Y) mit xa Welt und Y eine Reihe von Welten. Es wurde von der Game Logic of Parikh [1985] inspiriert, einer Interpretation von PDL mit „Programmen als Spiele“. Game Logic bietet ein zusätzliches Programmkonstrukt, das Programme dualisiert und es somit ermöglicht, den Schnittpunkt von Programmen als das Dual der nicht deterministischen Wahl zwischen Programmen zu definieren.

5. Schlussfolgerung

Dieser Artikel hat sich auf die aussagekräftige dynamische Logik und einige ihrer wesentlichen Varianten konzentriert. Mittlerweile gibt es eine Reihe von Büchern - Goldblatt [1982], Goldblatt [1992a], Harel [1979] und Harel, Kozen und Tiuryn [2000] - und Umfragepapiere - Harel [1984], Kozen und Tiuryn [1990], Parikh [1983] -Behandlung von PDL und verwandten Formalismen. Die Forschung zu PDL ist sicherlich maßgeblich an der Entwicklung vieler logischer Theorien zur Systemdynamik beteiligt. Diese Theorien liegen jedoch wohl außerhalb des Rahmens dieses Artikels. Van Eijck und Stokhof [2006] bieten einen neueren Überblick über Themen, die dynamische Logik verwenden, und befassen sich mit verschiedenen Themen, die für Philosophen von besonderem Interesse sind: z. B. Kommunikationsdynamik oder Semantik natürlicher Sprache. Neuere Bücher enthalten viele Details zu neueren Themen.wie die dynamische Logik des Wissens (dynamische epistemische Logik) in Van Ditmarsch, Van Der Hoek und Kooi [2007] und die dynamische Logik kontinuierlicher und hybrider Systeme (differentielle dynamische Logik) in Platzer [2010]. PDL wurde hauptsächlich zum Nachdenken über Programme konzipiert. Es gibt viele andere Anwendungen der Modallogik, um über Programme nachzudenken. Algorithmische Logik ist näher an PDL, da man explizit über Programme sprechen kann. Der Leser ist eingeladen, die in Mirkowska und Salwicki [1987] untersuchten Arbeiten zu konsultieren. Zeitliche Logik ist heute die Hauptlogik in der theoretischen Informatik und steht in engem Zusammenhang mit der Logik von Programmen. Sie ermöglichen es, das zeitliche Verhalten von Übergangssystemen mit einer Sprache auszudrücken, die von den Bezeichnungen (daher den Programmen) abstrahiert. Siehe zum Beispiel Schneider [2004] für einen Überblick über die Grundlagen in diesem Forschungsbereich.

Literaturverzeichnis

• Apt, K., 1981, „Zehn Jahre Hoares Logik: Eine Umfrage - Teil I“, ACM Transactions on Programming Languages and Systems, 3 (4): 431–483.
• Balbiani, P. und D. Vakarelov, 2003, "PDL mit Schnittmenge von Programmen: eine vollständige Axiomatisierung", Journal of Applied Non-Classical Logics, 13: 231-276.
• van Benthem, J., 1998, „Programmkonstruktionen, die für die Bisimulation sicher sind“, Studia Logica, 60: 311–330.
• Berman, F. und M. Paterson, 1981, „Propositional Dynamic Logic ist ohne Tests schwächer“, Theoretical Computer Science, 16: 321–328.
• Burstall, R., 1974, „Programmprüfung als Handsimulation mit geringer Induktion“, Informationsverarbeitung 74: Proceedings of IFIP Congress 74, Amsterdam: North Holland Publishing Company, 308–312.
• Danecki, R., 1984a, "Propositionelle dynamische Logik mit starkem Schleifenprädikat", in M. Chytil und V. Koubek, Mathematische Grundlagen der Informatik, Berlin: Springer-Verlag, 573-581.
• –––, 1984b, „Nichtdeterministische aussagekräftige dynamische Logik mit Schnittmenge ist entscheidbar“, in A. Skowron (Hrsg.), Computation Theory, Berlin: Springer-Verlag, 34-53.
• De Giacomo, G. und F. Massacci, 2000, „Kombination von Deduktion und Modellprüfung in Tableaus und Algorithmen für Converse-PDL“, Information and Computation, 160: 109–169.
• van Ditmarsch, H., W. van Der Hoek und B. Kooi, 2007, Dynamische epistemische Logik, Dordrecht: Springer-Verlag.
• van Eijck, J. und M. Stokhof, 2006, "The Gamut of Dynamic Logics", in D. Gabbay und J. Woods (Hrsg.), The Handbook of History of Logic, Band 7 - Logik und die Modalitäten in der 20. Jahrhundert, Amsterdam: Elsevier, 499–600.
• Emerson, E. und Jutla, C., 1988, "The Complexity of Tree Automata and Logics of Programs (Extended Abstract)", in Proceedings des 29. jährlichen Symposiums über Grundlagen der Informatik, Los Alamitos, CA: IEEE Computer Society 328–337.
• –––, 1999, „Die Komplexität von Baumautomaten und die Logik von Programmen“, im SIAM Journal of Computing, 29: 132–158.
• Engeler, E., 1967, „Algorithmische Eigenschaften von Strukturen“, Mathematical Systems Theory, 1: 183–195.
• Fischer, M. und R. Ladner, 1979, „Propositional Dynamic Logic of Regular Programs“, Journal of Computer and System Sciences, 18: 194–211.
• Floyd, R., 1967, „Zuweisen von Bedeutung zu Programmen“, Proceedings of the American Mathematical Society Symposia on Applied Mathematics (Band 19), Providence, RI: American Mathematical Society, 19–31.
• Gargov, G. und S. Passy, 1988, „Determinismus und Schleifen in kombinatorischer PDL“, Theoretical Computer Science, Amsterdam: Elsevier, 259–277.
• Goldblatt, R., 1982, Axiomatisierung der Logik der Computerprogrammierung, Berlin: Springer-Verlag.
• –––, 1992a, Logik der Zeit und Berechnung, Stanford: Zentrum für das Studium von Sprach- und Informationspublikationen.
• –––, 1992b, „Parallele Aktion: Gleichzeitige dynamische Logik mit unabhängigen Modalitäten“, Studia Logica, 51: 551–578.
• Göller, S., M. Lohrey und C. Lutz, 2007, „PDL mit Schnittpunkt und Umkehrung ist 2EXP-vollständig“, Grundlagen der Softwarewissenschaft und Computerstrukturen, Berlin: Springer, 198–212.
• Harel, D., 1979, Dynamische Logik erster Ordnung, Berlin: Springer-Verlag.
• –––, 1983, „Wiederkehrende Dominosteine: Das Unentscheidbare hoch verständlich machen“, in M. Karpinski (Hrsg.), Grundlagen der Berechnungstheorie, Berlin: Springer-Verlag, 177–194.
• –––, 1984, „Dynamic Logic“, in D. Gabbay und F. Guenthner (Hrsg.), Handbook of Philosophical Logic (Band II), Dordrecht: D. Reidel, 497–604.
• Harel, D., D. Kozen und J. Tiuryn, 2000, Dynamic Logic, Cambridge, MA: MIT Press.
• Harel, D. und Sherman, R., 1982, „Looping vs. Repeating in Dynamic Logic“, Information and Control, 55: 175–192.
• Hoare, C., 1969, „Eine axiomatische Grundlage für die Computerprogrammierung“, Mitteilungen der Association of Computing Machinery, 12: 576–580.
• Kozen, D., 1983, "Results on the Propositional μ-Calculus", Theoretical Computer Science, 27: 333–354.
• Kozen, D. und R. Parikh, 1981, „Ein elementarer Beweis für die Vollständigkeit von PDL“, Theoretical Computer Science, 14: 113–118.
• Kozen, D. und J. Tiuryn, 1990, "Logics of Programs", in J. Van Leeuwen (Hrsg.), Handbook of Theoretical Computer Science (Band B), Amsterdam: Elsevier, 789–840.
• Lange, M., 2005, "Eine geringere Komplexität für propositionelle dynamische Logik mit Schnittmenge", in R. Schmidt, I. Pratt-Hartmann, M. Reynolds und H. Wansing (Hrsg.), Advances in Modal Logic (Band 5)), London: King's College Publications, 133–147.
• Lange, M. und C. Lutz, 2005, „2-EXPTIME-Untergrenzen für aussagekräftige dynamische Logik mit Schnittmenge“, Journal of Symbolic Logic, 70: 1072–1086.
• Lutz, C., 2005, "PDL mit Schnittpunkt und Umkehrung ist entscheidbar". In L. Ong (Hrsg.), Informatiklogik, Berlin: Springer-Verlag, 413-427.
• Massacci, F., 2001, "Entscheidungsverfahren für expressive Beschreibungslogiken mit Schnittmenge, Zusammensetzung, Rollenumkehr und Rollenidentität", in B. Nebel (Hrsg.), 17. Internationale gemeinsame Konferenz über künstliche Intelligenz, San Francisco: Morgan Kaufmann, 193–198.
• Mirkowska, G. und A. Salwicki, 1987, Algorithmic Logic, Dordrecht: D. Reidel.
• Nishimura, H., 1979, „Sequentielle Methode in der aussagekräftigen dynamischen Logik“, Acta Informatica, 12: 377–400.
• Parikh, R., 1978, "Die Vollständigkeit der aussagekräftigen dynamischen Logik", in J. Winkowski (Hrsg.), Mathematische Grundlagen der Informatik, Berlin: Springer-Verlag, 1978, 403-415.
• –––, 1983, „Aussagenlogik von Programmen: neue Richtungen“, in M. Karpinski (Hrsg.), Grundlagen der Berechnungstheorie, Berlin: Springer-Verlag, 347-359.
• –––, 1985, „Die Logik der Spiele und ihre Anwendungen“, Annals of Discrete Mathematics, 24: 111–140.
• Peleg, D., 1987, "Concurrent Dynamic Logic", Journal der Association of Computing Machinery, 34: 450–479.
• Platzer, A., 2010, Logische Analyse hybrider Systeme: Theoreme für komplexe Dynamik beweisen, Berlin: Springer, 2010.
• Pratt, V., 1976, „Semantische Überlegungen zur Floyd-Hoare-Logik“, in Proceedings des 17. IEEE-Symposiums über Grundlagen der Informatik, Los Alamitos, CA: IEEE Computer Society, 109–121.
• –––, 1978, „Eine praktische Entscheidungsmethode für aussagekräftige dynamische Logik“, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, New York, NY: ACM, 326–337.
• –––, 1980a, „Eine nahezu optimale Methode zum Nachdenken über Maßnahmen“, Journal of Computer and System Sciences, 20: 231–254.
• –––, 1980b, „Anwendung der Modallogik auf die Programmierung“, Studia Logica, 39: 257–274.
• Sakalauskaite, J. und M. Valiev, 1990, „Vollständigkeit der aussagekräftigen dynamischen Logik mit unendlicher Wiederholung“, in P. Petkov (Hrsg.), Mathematical Logic, New York: Plenum Press, 339–349.
• Salwicki, A., 1970, „Formalisierte algorithmische Sprachen“, Bulletin de l'Academie Polonaise des Sciences, Serie des Sciences Mathematiques, Astronomiques et Physiques, 18: 227–232.
• Segerberg, K., 1977, "Ein Vollständigkeitssatz in der Modallogik von Programmen", Notices of the American Mathematical Society, 24: 522.
• Schneider, K., 2004, Verifikation reaktiver Systeme, Berlin: Springer-Verlag.
• Streett, R., 1982, „Die aussagekräftige dynamische Logik von Schleifen und Umkehrungen ist elementar entscheidbar“, Information and Control, 54: 121–141.
• Vakarelov, D., 1983, „Filtrationssatz für dynamische Algebren mit Tests und inversem Operator“, in A. Salwicki (Hrsg.), Logik von Programmen und ihren Anwendungen, Berlin: Springer-Verlag, 314–324.
• Vardi, M., 1985, „The Taming of Converse: Argumentation über Zwei-Wege-Berechnungen“, in Lecture Notes in Computer Science (Band 193), Berlin-Heidelberg: Springer, 413–423.
• –––, 1998, „Mit Zwei-Wege-Automaten über die Vergangenheit nachdenken“, in Lecture Notes in Computer Science (Band 1443), Berlin-Heidelberg: Springer, 628–641.
• Vardi, M. und Stockmeyer, L., 1985, "Verbesserte Ober- und Untergrenzen für die Modallogik von Programmen: Vorläufiger Bericht", in Proceedings of the 17. Annual ACM Symposium on Theory of Computing, New York, NY: ACM, 240 –251.
• Yanov, J., 1959, „Zur Äquivalenz von Operatorschemata“, Problems of Cybernetic, 1: 1–100.

Akademische Werkzeuge

	Wie man diesen Eintrag zitiert.
	Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
	Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
	Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

[Bitte kontaktieren Sie den Autor mit Vorschlägen.]