Computation Tree Logic

Datei:Computational Tree Logic Example.png

CTL-Formeln visualisiert

Die Computation Tree Logic (kurz CTL) ist eine Temporale Logik, deren Modell der Zeit eine baumartige Struktur hat. Die zeitliche Änderung von Zuständen und deren Eigenschaften wird durch Pfade innerhalb dieser Baumstruktur modelliert. Hierbei hat die Zukunft mehrere Pfade, wobei nicht festgelegt ist, welche letztendlich realisiert werden. Demnach können Aussagen über die mögliche Entwicklungen getroffen werden.

Die CTL wird zur Verifikation von Hard- und Software verwendet, üblicherweise von Model Checkern.

Zu der Familie der temporalen Logiken gehört auch die Linear temporale Logik (LTL), wobei hier nur eine Zukunft möglich ist. Eine Verallgemeinerung der beiden Logiken wird als CTL* bezeichnet.

Syntax

Minimale Grammatik

Sei $AP$ eine Menge von atomaren Aussagen (Behauptungen), dann ist jedes Element $p\in AP$ eine CTL-Formel. Sind $\varphi$ und $\psi$ Formeln, dann auch $\mathrm{\neg }\varphi$, $\varphi \vee \psi$, $\text{EX}\varphi$, $\text{EG}\varphi$ und $\varphi \text{EU}\psi$. Dies definiert die minimale Grammatik von CTL. In der Regel wird diese allerdings um die gängigen booleschen Operatoren $\wedge$, $⟹$und $\iff$, sowie einigen weiteren temporalen Operatoren erweitert.

Temporale Operatoren

Die Erweiterung der minimalen Grammatik um folgende Operatoren erhöht nicht die Mächtigkeit der Sprache, da alle Operatoren durch Umformungen zurückgeführt werden können.

• Pfadoperatoren:
  • $A\varphi$ – auf allen Pfaden folgt $\varphi$ (englisch: All)
  • $E\varphi$ – auf mindestens einem Pfad folgt $\varphi$ (englisch: Exists)
• Pfad-spezifische Operatoren:
  • $X\varphi$ – unmittelbar folgt $\varphi$ (englisch: neXt state)
  • $F\varphi$ – irgendwann folgt $\varphi$ (englisch: some Future state oder Finally)
  • $G\varphi$ – auf dem folgenden Pfad folgt in jedem Zustand $\varphi$ (englisch: Globally)
  • $\varphi U\psi$ – $\varphi$ folgt bis zum Erreichen des Zustands $\psi$ (englisch: Until)
  • $\varphi W\psi$ – $\varphi$ folgt immer oder bis zum Erreichen des Zustands $\psi$ (englisch: Weak Until)

Pfad und pfad-spezifische Operatoren können miteinander kombiniert werden, sodass sich beispielsweise folgende Formeln ergeben:

• $EX\varphi$ – in (mind.) einem nächsten Zustand gilt $\varphi$
• $EF\varphi$ – in (mind.) einem der folgenden Zustände gilt $\varphi$
• $EG\varphi$ – es gibt (mind.) einen Pfad, so dass $\varphi$ entlang des ganzen Pfades gilt
• $E[\varphi U\psi ]$ – es gibt einen Pfad, für den gilt: bis zum ersten Auftreten von $\psi$ gilt $\varphi$
• $AX\varphi$ – in jedem nächsten Zustand gilt $\varphi$
• $AF\varphi$ – man erreicht immer einen Zustand, in dem $\varphi$ gilt
• $AG\varphi$ – auf allen Pfaden gilt in jedem Zustand $\varphi$
• $A[\varphi U\psi ]$ – es gilt immer $\varphi$ bis zum ersten Auftreten von $\psi$

Semantik

CTL Formeln werden über Transitionssysteme definiert. Für eine gegebene Folge von Zuständen des Systems $T(s_0)=s_0,s_1,\dots$ (beginnend in Zustand $s_0$) sind die Operatoren formal wie folgt definiert, dabei steht $T(s_0)\models \varphi$ für $T(s_0)$ erfüllt $\varphi$:

• $T(s_0)\models \mathrm{\neg }\varphi \iff T(s_0)\models ̸\varphi$
• $T(s_0)\models \varphi \vee \psi \iff T(s_0)\models \varphi \text{ oder }T(s_0)\models \psi$
• $T(s_0)\models EX\varphi \iff T(s_1)\models \varphi$
• $T(s_0)\models EG\varphi \iff \mathrm{\forall }i:T(s_i)\models \varphi$
• $T(s_0)\models \varphi EU\psi \iff \mathrm{\exists }k:T(s_k)\models \psi \wedge \mathrm{\forall }i<k:T(s_i)\models \varphi$

Die oben genannten Umformungen erlauben es, Formeln ineinander umzuwandeln.

• $\mathrm{\neg }A\varphi \equiv E\mathrm{\neg }\varphi$
• $\mathrm{\neg }AF\varphi \equiv EG\mathrm{\neg }\varphi$
• $\mathrm{\neg }EF\varphi \equiv AG\mathrm{\neg }\varphi$
• $\mathrm{\neg }AX\varphi \equiv EX\mathrm{\neg }\varphi$
• $AG\varphi \equiv \varphi \wedge AXAG\varphi$
• $EG\varphi \equiv \varphi \wedge EXEG\varphi$
• $AF\varphi \equiv \varphi \vee AXAF\varphi$
• $EF\varphi \equiv \varphi \vee EXEF\varphi$
• $A[\varphi U\psi ]\equiv \psi \vee (\varphi \wedge AXA[\varphi U\psi ])$
• $E[\varphi U\psi ]\equiv \psi \vee (\varphi \wedge EXE[\varphi U\psi ])$

Literatur

• Clarke, Grumberg, Peled: Model Checking. MIT Press, 2000, ISBN 0-262-03270-8
• Rohit Kapur: CTL for Test Information of Digital ICS. Springer, 2002, ISBN 978-1-4020-7293-2
• B. Berard, Michel Bidoit, Alain Finkel: Systems and Software Verification. Model-checking Techniques and Tools. Springer, 2001, ISBN 3-540-41523-8
• M. Huth and M. Ryan: Logic in Computer Science - Modelling and Reasoning about Systems. Cambridge, 2004, ISBN 0-521-54310-X