View
7
Download
0
Category
Preview:
Citation preview
Temporale Logik und Bisimulation
Julian Fietkau, Nils Kubera, Dominik Nuszpl
Universität Hamburg
2. Februar 2011
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 1 / 28
Organisatorisches vorweg
Diese Folien sind unter CC-BY-SA 3.0 freigegeben.
Folien-Download und Feedback-Möglichkeit:
http://www.julian-fietkau.de/temporale_logik_und_bisimulation
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 2 / 28
Inhaltsverzeichnis
Übersicht
1 Bisimulation in TransitionssystemenEinleitungZwei verschiedene GetränkeautomatenWas ist Bisimulation?Noch mal die Getränkeautomaten
2 Temporale Logik, Folgen- und LTL-ÄquivalenzLTL, CTL und CTL*CTL* Gültigkeit und Äquivalenz
3 Bisimulation in Beziehung zu CTL- und CTL*-ÄquivalenzBeweis ≡CTL∗ = ≡CTL = ∼TSFazit
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 3 / 28
Bisimulation in Transitionssystemen Einleitung
Einleitung
Wir betrachten Transitionssysteme als Werkzeug zur Spezifikation undModellierung.
Definition 1: TransitionssystemTS = (S,A, tr , S0,SF )Im Folgenden meist vereinfacht verwendet: TS = (S,A, tr , s0) (Nur einStartzustand, keine Endzustände)
Um Gesetzmäßigkeiten im Verhalten verschiedener Transitionssystemeerkennen und beschreiben zu können, untersuchen wir verschiedene Artender Äquivalenz, nämlich Folgenäquivalenz und Bisimulation.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 4 / 28
Bisimulation in Transitionssystemen Zwei verschiedene Getränkeautomaten
Kaffee oder Tee?
s0
s1
s2 s3
{bezahlen}
{Tee}{Kaffee}
s0
s1
s3 s4
{bezahlen}
{Tee}{Kaffee}
s2
TS1 TS2
Kaffee
Tee
Kaffee
Tee
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 5 / 28
Bisimulation in Transitionssystemen Zwei verschiedene Getränkeautomaten
Gemeinsame Zustandsfolgen
Welche Zustandsfolgen sind in den Transitionssystemen möglich?w1 = (bezahlen,Kaffee, bezahlen,Kaffee, bezahlen,Tee)w2 = (bezahlen,Tee, bezahlen,Tee, bezahlen,Tee, . . . )
Behauptung: Jede Folge, die in TS1 möglich ist, ist auch in TS2 möglichund umgekehrt. Die beiden Transisionssysteme sind folgenäquivalent.(Der Beweis bleibt dem Leser zur Übung überlassen.)
Bedeutet das, dass die beiden TS in jeder Hinsicht gleich sind? Nein! Wirkönnen sinnvolle Äquivalenzkriterien finden, nach denen sie verschiedensind.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 6 / 28
Bisimulation in Transitionssystemen Was ist Bisimulation?
Definition
Definition 2: (Zustandsbasierte) BisimulationTS1 = (S1,A, tr1,S0
1 ) und TS2 = (S2,A, tr2, S02 ) sind bisimilar genau dann,
wenn eine binäre Relation („Bisimulation“) B ⊆ S1 × S2 existiert, so dassgilt:
1 ∀s0 ∈ S01 ∃r0 ∈ S0
2 : (s0, r0) ∈ B∀r0 ∈ S0
2 ∃s0 ∈ S01 : (s0, r0) ∈ B
2 Für alle (r1, s1) ∈ B gilt:r2 ∈ Post(r1)⇒ ∃s2 ∈ Post(s1) : (r2, s2) ∈ Bs2 ∈ Post(s1)⇒ ∃r2 ∈ Post(r1) : (r2, s2) ∈ BL(r1) = L(s1)
Hierbei ist L eine Etikettierungsfunktion, die den (relevanten) ZuständenBezeichnungen zuordnet. Post(s) ist die Menge der von s aus direkterreichbaren Nachfolgezustände.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 7 / 28
Bisimulation in Transitionssystemen Was ist Bisimulation?
Ein Beispiel
s0
s1
s2 s3
{bezahlen}
{Tee}{Kaffee}
s4 {Tee}
TS3
TS1 und TS3 sind bisimilar.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 8 / 28
Bisimulation in Transitionssystemen Noch mal die Getränkeautomaten
Kaffee oder Tee? – eine genauere Analyse
Betrachte TS1 und TS2:
1 (s0, s′0) ∈ B, erste Teilbedingung ist damit erfüllt.
2 Nun muss weiterhin gelten: (s1, s′i ) ∈ B mit i ∈ {1, 2}
(Nachfolger von s ′0)3 Da s3 ∈ Post(s1) und (s1, s
′1) ∈ B und s ′3 ∈ Post(s ′1) mit
|Post(s ′1)| = 1, folgt zwangsweise: (s3, s′3) ∈ B
4 Jedoch ist L(s3) 6= L(s ′3)
TS1 und TS2 sind nicht bisimilar.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 9 / 28
Bisimulation in Transitionssystemen Noch mal die Getränkeautomaten
Fazit
Folgenäquivalenz macht Aussagen über das Verhalten der Systemevon außen betrachtet. Bisimulation beschreibt zusätzlich die interneStruktur.Bisimulation impliziert automatisch auch Folgenäquivalenz:TSa ∼ TSb ⇒ TSa ≡trace TSb(TSa ≡trace TSb ; TSa ∼ TSb)
Systeme, die die gleichen Zustandsfolgen erlauben, sind nichtunbedingt verhaltensäquivalent.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 10 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz LTL, CTL und CTL*
LTL
©ϕ: nächster Zustand erfüllt ϕ♦ϕ : irgendein Folgezustand erfüllt ϕ�ϕ : alle folgenden Zustände erfüllen ϕϕ1 ∪ ϕ2 : ϕ1 gilt bis in einem Folgezustand ϕ2 erfüllt istLTL Formeln
Definition 3: LTL-Formelnϕ ≡ true | false | a | ϕ1 ∨ ϕ2 | ϕ1 ∧ ϕ2 | ¬ϕ | ©ϕ | ♦ϕ | �ϕ | ϕ1 ∪ ϕ2
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 11 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz LTL, CTL und CTL*
CTL und CTL*
zusätzlich Zustandsformeln mit Quantoren, die sich auf alle vomZustand ausgehenden Pfade beziehenQuantoren
∀ϕ : entlang aller Pfade gilt ϕ∃ϕ : entlang mindestens eines Pfads gilt ϕ
CTL ist eine Teilmenge von CTL*.Jeder Temporaloperator wird durch genau einen Pfadquantorquantifiziert.
∃© ϕ : in mind. einem nächsten Zustand gilt ϕ∃♦ϕ : in mind. einem der folgenden Zustände gilt ϕ∃�ϕ : es gibt mind. einen Pfad, in dem ϕ entlang des komplettenPfades gilt...∀© ϕ : in jedem nächsten Zustand gilt ϕ...
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 12 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz LTL, CTL und CTL*
Verhältnis zwischen LTL, CTL und CTL∗
∀�∃♦a �♦a ♦(a ∧©a)
CTL LTL
♦(a ∧©a) ∨ ∀�∃♦a
CTL∗
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 13 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz CTL* Gültigkeit und Äquivalenz
Gültigkeit für CTL*-Zustandsformeln
Sei TS := (S,Act,→, I,AP, L) ein Transitionssystem ohne Endzustände, s∈ S ein Zustand, Φ und Ψ CTL*-Zustandsformeln und ϕ,ϕ1 und ϕ2CTL*-Pfadformeln.Definition 4: Gültigkeit von ZustandsformelnDie Gültigkeit |= für CTL*-Zustandsformeln wird definiert durch
s |= a⇔ a ∈ L(s),s |= ¬Φ⇔ not s |= Φ,s |= Φ ∧Ψ⇔ (s |= Φ) and (s |= Ψ),s |= ∃ϕ⇔ π |= ϕ für mind. einen Pfad beginnend in s,s |= ∀ϕ⇔ π |= ϕ für alle Pfade beginnend in s
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 14 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz CTL* Gültigkeit und Äquivalenz
Gültigkeit für CTL*-Pfadformeln
Sei π = s0s1s2... ein Pfad und π[i ..] mit i ≥ 0 ein Teilpfad von πbeginnend bei Index i.
Definition 5: Gültigkeit von PfadformelnDie Gültigkeit |= für CTL*-Pfadformeln wird definiert durch
π |= Φ⇔ s0 |= Φ,π |= ϕ1 ∧ ϕ2 ⇔ π |= ϕ1 and π |= ϕ2,π |= ¬ϕ⇔ π 6|= ϕ,π |=©ϕ⇔ π[1..] |= ϕ,π |= ϕ1 ∪ ϕ2 ⇔ ∃j ≥ 0.(π[j ..] |= ϕ2 ∧ (∀0 ≤ k < j .π[k..] |= ϕ1)),
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 15 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz CTL* Gültigkeit und Äquivalenz
CTL*-Äquivalenz in Transitionssystemen
Seien TS, TS1 und TS2 Transitionssysteme ohne Endzustände.
Definition 6: ≡CTL∗ für ZuständeFür Zustände s1, s2 in TS gilt:s1 ≡CTL∗ s2, wenns1 |= Φ⇔ s2 |= Φ für alle CTL*-Zustandfomeln Φ über AP.
Definition 7: ≡CTL∗ für TransitionssystemeFür TS1,TS2 gilt:TS1 ≡CTL∗ TS2, wennTS1 |= Φ⇔ TS2 |= Φ für alle CTL*-Zustandfomeln Φ über AP.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 16 / 28
Temporale Logik, Folgen- und LTL-Äquivalenz CTL* Gültigkeit und Äquivalenz
Folgenäquivalenz ⊆ LTL-Äquivalenz
Zu zeigen: ≡trace ⊆ ≡LTL
Sei TS ein Transitionssystem ohne Endzustände und s1, s2 Zuständein TS.Wenn s1 6≡CTL s2, existiert eine CTL-Zustandsformel Φ mit s1 |= Φund s2 6|= Φ.Dies gilt analog für CTL*, aber nicht für LTL.
Beweis: Folgenäquivalenz ⊆ LTL-ÄquivalenzAngenommen s1 6≡LTL s2 und Folgen(s1) ist eine echte Teilmenge vonFolgen(s2). Dann gelten alle LTL Formeln, die für s2 gelten, ebenso für s1.Da jedoch in Folgen(s2) Folgen enthalten sind, die nicht in Folgen(s1)existieren, gibt es eine LTL-Formel ϕ mit s2 |= ϕ aber s1 6|= ϕ. �
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 17 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Äquivalenzrelationen für Transitionssysteme
Zu Zeigen für endliche Transitionssysteme ohne Endzustände:
≡CTL∗ = ≡CTL = ∼TS
Beweis in drei Schritten.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 18 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Die feiner/gröber-Beziehung
Seien ∼a und ∼b Äquivalenzrelationen über der gleichen Menge S.
Definition 8: feiner/gröber-Beziehung∼a ist feiner als ∼b, wenn für alle s1, s2 ∈ S gilt:s1 ∼a s2 ⇒ s1 ∼b s2.Geschrieben ∼a ⊆ ∼b.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 19 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
≡CTL∗ ist feiner als ≡CTL
Für s1, s2 ∈ S:
Beweis: ≡CTL∗ ⊆ ≡CTL
Zu Zeigen:
s1 ≡CTL∗ s2 ⇒ s1 ≡CTL s2
Gibt es keine Formel Φ in CTL∗ mit s1 |= Φ und s2 6|= Φ (oder umgekehrt),so kann es auch keine in CTL geben, da CTL ⊆ CTL∗.Entspricht ¬(s1 ≡CTL∗ s2 ∧ ¬(s1 ≡CTL s2)) was äquivalent zur Vermutungist.Es folgt nach Definition 8:≡CTL∗ ⊆ ≡CTL �
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 20 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
≡CTL ist feiner als ∼TS
Zu Zeigen: s1 ≡CTL s2 ⇒ s1 ∼TS s2
Beweiskonzept: ≡CTL ⊆ ∼TS
Relation R = {(s1, s2) ∈ S × S|s1 ≡CTL s2}Damit die Annahme gilt, muss R die Punkte 1 – 3 der Definition 2.2erfüllen.Punkt 1: Da Label L(s) die atomaren Formeln darstellen, müssenCTL-äquivalente Formeln die gleichen Label besitzen. L(s1) = L(s2).Punkt 2 und 3: Gilt für Formelmenge Ψ:s ′1 |= Ψ dann gilt s1 |= ∃©Ψ. Da (s1, s2) ∈ R gilt s2 |= ∃©Ψ und esgibt ein s ′2 |= Ψ, womit (s ′1, s ′2) ∈ R. �
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 21 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
∼TS ist feiner als ≡CTL∗
Zu Zeigen: s1 ∼TS s2 ⇒ s1 ≡CTL∗ s2
Beweiskonzept: ∼TS ⊆ ≡CTL∗
Seien s1, s2 Zustände in TS, π1, π2 unendliche TeilpfadeZu Zeigen:
a Wenn s1 ∼TS s2, dann gilt für jede CTL* FormelΦ : s1 |= Φ⇔ s2 |= Φ
b Wenn π1 ∼TS π2, dann gilt für jede CTL* Pfad-Formelγ : π1 |= γ ⇔ π2 |= γ
Beweis erfolgt per Induktion über Formelstruktur.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 22 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Induktionsbeweis ∼TS ist feiner als ≡CTL∗ (1)Es gelte: s1 ∼TS s2.(a) Induktionsbasis:Für Φ = true gilt Annahme a.Da L(s1) = L(s2) gilt, gilt für Φ = a ∈ AP:
s1 |= a⇔ a ∈ L(s1)⇔ a ∈ L(s2)⇔ s2 |= aInduktionsschritt:
1 Φ = Φ1 ∧ Φ2.
s1 |= Φ1 ∧ Φ2 ⇔ s1 |= Φ1 and s1 |= Φ2
⇔ s2 |= Φ1 and s2 |= Φ2 ⇔ s2 |= Φ1 ∧ Φ2
2 Φ = ¬Ψ.
s1 |= ¬Ψ⇔ s1 6|= Ψ
⇔ s2 6|= Ψ⇔ s2 |= ¬ΨJulian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 23 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Induktionsbeweis ∼TS ist feiner als ≡CTL∗ (2)
3 Φ = ∃γ. Es reicht zu zeigen:
s1 |= ∃γ =⇒ s2 |= ∃γ
Lässt sich über Pfadeigenschaften der Bisimulation zeigen.
(b) Induktion über Pfade entsprechend für die Formeln:
γ = Φ, γ = γ1 ∧ γ2, γ = ¬ψ, γ =©ψ, γ = γ1Uγ2
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 24 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Da gilt:
∼TS ⊆ ≡CTL∗ ⊆ ≡CTL ⊆ ∼TS
gilt:
≡CTL∗ = ≡CTL = ∼TS
Was bedeutet: Bisimilare Transitionssysteme erfüllen die gleichen CTL*-und CTL-Formeln.
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 25 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Beweis ≡CTL∗ = ≡CTL = ∼TS
Beispiel
TS1 6∼TS TS2, TS1 ∼TS TS3
TS1 TS2 TS3∃© (∃© Kaffee ∧ ∃© Tee)
√×
√
¬∃© (∃© Kaffee ∧ ∃© Tee) ×√
×∃© (∃© Kaffee ∨ ∃© Tee)
√ √ √
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 26 / 28
Bisimulation in Beziehung zu CTL- und CTL*-Äquivalenz Fazit
Fazit
Es existieren verschiedene Äquivalenzrelationen fürTransitionssysteme, wie Folgenäquivalenz, Bisimulation, ≡LTL, ≡CTL,≡CTL∗ , die teilweise äquivalent zueinander sind.Diese Äquivalenzen lassen sich beispielsweise beim Model Checkingeinsetzen, um die Komplexität zu verringern.(Bsp.: Formel Φ wird in Bisimulationsquotient von TS nicht erfüllt→ TS 6|= Φ.)
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 27 / 28
Ende
Ende
Danke für die Aufmerksamkeit!
Julian Fietkau, Nils Kubera, Dominik Nuszpl Temporale Logik und Bisimulation 02.02.11 28 / 28
Recommended