Temporale und Modale Logik in der Informatik

Temporale und modale Logiken erweitern die klassische Logik um Operatoren für Zeit und Möglichkeit. Sie bieten präzise Sprachen, um zu spezifizieren, wie sich ein Programm oder ein reaktives System über seine gesamte Ausführung hinweg verhalten muss.

Definition

Die temporale Logik erweitert die propositionale oder prädikatenlogische Logik um Operatoren, die beschreiben, wann Eigenschaften entlang einer Berechnung gelten, z. B. immer, schließlich und bis; die modale Logik verallgemeinert dies mit Operatoren für Notwendigkeit und Möglichkeit über eine Struktur von Zuständen und Übergängen.

Scope

Dieses Thema behandelt lineare und verzweigende temporale Logiken wie LTL und CTL, modale Logiken einschließlich der dynamischen Logik und des modalen My-Kalküls, die Formulierung von Sicherheits- und Lebendigkeitseigenschaften sowie die algorithmischen Probleme der Modellprüfung und Erfüllbarkeit, die diese Logiken für die automatisierte Verifikation zentral machen.

Core questions

• Wie kann eine Logik ausdrücken, dass etwas Gutes schließlich geschieht oder dass etwas Schlechtes niemals geschieht?
• Worin besteht der Unterschied zwischen dem Schlussfolgern über eine einzelne Ausführung und über alle möglichen zukünftigen Zustände?
• Wie wird die Überprüfung, ob ein System eine temporale Eigenschaft erfüllt, algorithmisch gestaltet?
• Welche temporalen Logiken bieten ein ausgewogenes Verhältnis zwischen Ausdruckskraft und effizienter Verifikation?

Key theories

Temporale Logik für die Programmspezifikation

Pnueli zeigte, dass die temporale Logik die Korrektheit reaktiver und nebenläufiger Programme erfasst, indem sie Eigenschaften über deren Ausführungen ausdrückt und eine einheitliche Sprache für Sicherheits- und Lebendigkeitsanforderungen bereitstellt.

Modellprüfung von Verzweigungszeitlogik

Clarke und Emerson führten die Computation Tree Logic (CTL) und einen Algorithmus ein, um diese automatisch gegen ein Endzustandsmodell zu verifizieren, und begründeten damit das Feld der Modellprüfung.

Clinical relevance

Temporale Logiken sind die Spezifikationssprachen von Modellprüfern, die routinemäßig zur Verifikation von Hardware-Designs, Kommunikationsprotokollen und nebenläufiger Software eingesetzt werden, um Deadlocks und Verletzungen von Sicherheits- und Lebendigkeitseigenschaften vor der Bereitstellung zu erkennen; diese Technologie brachte ihren Urhebern den Turing Award ein und ist im Chipdesign Standard.

History

Pnueli schlug 1977 die temporale Logik für die Argumentation über Programme vor, und Clarke und Emerson, unabhängig davon Queille und Sifakis, entwickelten um 1981 die Modellprüfung. Der Ansatz wurde in den frühen 1990er Jahren durch symbolische Methoden auf industrielle Systeme skaliert, und seine Schöpfer erhielten für die Technik den Turing Award.

Key figures

• Amir Pnueli
• Edmund Clarke
• E. Allen Emerson
• Joseph Sifakis

Seminal works

• clarkeEmerson1981
• huthRyan2004

Frequently asked questions

Worin besteht der Unterschied zwischen Linearzeit- und Verzweigungszeitlogik?

Linearzeitlogiken wie LTL beschreiben Eigenschaften eines einzelnen, möglicherweise unendlichen Ausführungspfades. Verzweigungszeitlogiken wie CTL quantifizieren über den Baum aller möglichen zukünftigen Zustände von jedem Zustand aus, wodurch man ausdrücken kann, dass entlang eines Pfades oder entlang aller Pfade eine Eigenschaft gilt. Sie haben unterschiedliche Ausdrucksstärken und Verifikationsalgorithmen.

Wie nutzt die Modellprüfung diese Logiken?

Ein System wird als Endzustandsmodell und eine gewünschte Eigenschaft als temporale Logikformel dargestellt. Ein Modellprüfer untersucht erschöpfend die Zustände, um festzustellen, ob die Formel gilt, und falls nicht, erzeugt er eine Gegenbeispielspur, wodurch die Verifikation sowohl automatisch als auch diagnostisch wird.