Formale Fundierung und effizientere Implementierung der schrittbasierten TLDA-Interleavingsemantik

01/04/11

Formale Fundierung und e!zientere Implementierung der schrittbasierten TLDA-

InterleavingsemantikDiplomverteidigung

Niels Lohmann

[email protected]://www.informatik.hu-berlin.de/~nlohmann/studium

2

Diplom-verteidigung

Motivation der Arbeit

! Mit TLDA können verteilte Systeme spezifiziert werden. Und dann?

! Ziel: Modelchecker für TLDA

! Studienarbeit: Entwicklung und Implementierung einer Interleavingsemantik für TLDA

! Diplomarbeit: formale Fundierung und verbesserte Algorithmen

3

Diplom-verteidigung

Gliederung

1. Konsumenten-/Produzentensystem

2. Einführung in TLDA

3. Semantiken

4. Transitionssysteme

5. Formale Fundierung6. E!zientere Algorithmen

7. Ausblick

Konsumenten-/Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung

Effizientere Implementierung

Ausblick

4

Diplom-verteidigung


! Der Produzent produziertspontan einen Gegenstandund legt ihn im Pu"er ab.

! Der Pu!er kann höchstens einen Gegenstand aufnehmen.

! Der Konsument entnimmtspontan Gegenstand ausdem Pu"er und konsumiert ihn.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

5

Diplom-verteidigung

verteiltes System mit drei Komponenten:

! Produzent:


ready toconsume

ready toremove

filledempty

ready todeliver

ready toproduce

produce

deliver

filling

emptying

remove

consume


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

5

Diplom-verteidigung


! Produzent:

! Pu"er:


ready toconsume

ready toremove

filledempty

ready todeliver

ready toproduce

produce

deliver

filling

emptying

remove

consume


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

5

Diplom-verteidigung


! Produzent:

! Pu"er:

! Konsument:


ready toconsume

ready toremove

filledempty

ready todeliver

ready toproduce

produce

deliver

filling

emptying

remove

consume


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

5

Diplom-verteidigung


! Produzent:

! Pu"er:

! Konsument:

drei Systemvariablen:


ready toconsume

ready toremove

filledempty

ready todeliver

ready toproduce

produce

deliver

filling

emptying

remove

consume


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

6

Diplom-verteidigung


rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

6

Diplom-verteidigung


rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

6

Diplom-verteidigung


rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

6

Diplom-verteidigung


rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

7

Diplom-verteidigung

Einführung in TLDA

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

7

Diplom-verteidigung

Einführung in TLDA

Das semantische Modell ist ein Ablauf.

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

7

Diplom-verteidigung

Einführung in TLDA


! ein Schnitt kann als lokaler Zustand aufgefasst werden

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

7

Diplom-verteidigung

Einführung in TLDA


! ein Schnitt kann als lokaler Zustand aufgefasst werden

! jeder Ablauf hat einen Anfangsschnitt

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

8

Diplom-verteidigung

Einführung in TLDA

rp

0

rr

rd

§

rp t1 rd rp

t2 rc rr

1 0 1

…

…

…

C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

8

Diplom-verteidigung

Einführung in TLDA

rp

0

rr

rd

§

rp t1 rd rp

t2 rc rr

1 0 1

…

…

…

C!C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

8

Diplom-verteidigung

! wenn alle möglichen Transitionen schalten, wird der Nachfolgeschnitt C' erreicht

Einführung in TLDA

rp

0

rr

rd

§

rp t1 rd rp

t2 rc rr

1 0 1

…

…

…

C!C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

8

Diplom-verteidigung


! die Schnitte C, C' und die Transitionen bilden einen Schritt

Einführung in TLDA

rp

0

rr

rd

§

rp t1 rd rp

t2 rc rr

1 0 1

…

…

…

C!C


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

8

Diplom-verteidigung


! die Schnitte C, C' und die Transitionen bilden einen Schritt

Einführung in TLDA

rp

0

rr

rd

§

rp t1 rd rp

t2 rc rr

1 0 1

…

…

…

C!C

Dieser Schnitt kann nichtdurch Schritte erreicht werden


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

9

Diplom-verteidigung

! Halbordnungssemantik

Semantiken


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

s rp t rd rp

u rc rr

1 0 1

…

…

…

9

Diplom-verteidigung

! Halbordnungssemantik! Transitionen sind halbgeordnet:

Semantiken


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

s rp t rd rp

u rc rr

1 0 1

…

…

…

9

Diplom-verteidigung


! Transition s schaltet vor t

Semantiken


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

s rp t rd rp

u rc rr

1 0 1

…

…

…

9

Diplom-verteidigung


! Transition s schaltet vor t

! Transitionen t und u sind nebenläufig:es gibt keine Reihenfolge

Semantiken


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

s rp t rd rp

u rc rr

1 0 1

…

…

…

10

Diplom-verteidigung

Semantiken

Erst t, dann u!

rp1rr

t u


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

10

Diplom-verteidigung

Semantiken

Erst t, dann u!

rp1rr

t u

u tErst u, dann t!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

10

Diplom-verteidigung

Semantiken

Erst t, dann u!

rp1rr

t u

u t

{t, u}

Erst u, dann t!

t und u schalten gleichzeitig!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

rp1rr

rd0rc

10

Diplom-verteidigung

! Interleavingsemantik

Semantiken

Erst t, dann u!

rp1rr

t u

u t

{t, u}

Erst u, dann t!



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

rp1rr

rd0rc

10

Diplom-verteidigung

! Interleavingsemantik! betrachtet alle möglichen Reihenfolgen:

Semantiken

Erst t, dann u!

rp1rr

t u

u t

{t, u}

Erst u, dann t!



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

rp1rr

rd0rc

10

Diplom-verteidigung


! total geordnet

Semantiken

Erst t, dann u!

rp1rr

t u

u t

{t, u}

Erst u, dann t!



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

rp1rr

rd0rc

10

Diplom-verteidigung


! total geordnet! exponentielle Anzahl von Interleavings und

Zwischenzuständen

Semantiken

Erst t, dann u!

rp1rr

t u

u t

{t, u}

Erst u, dann t!



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rd1rr

rd0rc

rp1rr

rp0rc

rd0rc

rp1rr

rd0rc

11

Diplom-verteidigung

Semantiken

! Halbordnungssemantiken:+ sehr ausdrucksstark! kaum Erfahrungen bei der

computergestützten Verifikation

! Interleavingsemantiken:! Zustandsexplosion+ sehr einfach+ können leicht durch Graphen

(Transitionssysteme) repräsentiert werden+ explizites Modelchecking weit verbreitet


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

12

Diplom-verteidigung

Transitionssystem

Definition: TS = (S, S0, Act, R, L)

buff h 0 buff h 1 buff h 0

s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

12

Diplom-verteidigung

Transitionssystem

Definition: TS = (S, S0, Act, R, L)! S: Zustandsmenge


s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

12

Diplom-verteidigung

Transitionssystem


! S0 ! S: Menge der Anfangszustände


s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

12

Diplom-verteidigung

Transitionssystem



! Act: Aktionsmenge

buff h 0 buff h 1 buff h 0a0 a1

a3

s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

a2

12

Diplom-verteidigung

Transitionssystem



! Act: Aktionsmenge

! R ! S " Act " S: Übergangsrelation


a3

s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

a2

12

Diplom-verteidigung

Transitionssystem



! Act: Aktionsmenge

! R ! S " Act " S: Übergangsrelation

! L: S ! (Var ! Val): Zustandsbeschriftung


a3

s0 s1 s2


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

a2

13

Diplom-verteidigung

Transitionssystem

Wir können ein Transitionssystem TS! für

TLDA-Spezifikationen ! in Normalform bilden:


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

13

Diplom-verteidigung

Transitionssystem



! Definition: Normalform:! , Init # □ Next


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

13

Diplom-verteidigung

Transitionssystem



! Definition: Normalform:! , Init # □ Next

! Aktionsmenge:Act ist die Menge der Klauseln der disjunktiven Normalform von Next.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

14

Diplom-verteidigung

Transitionssystem

! Zustände, Anfangszustände, Beschriftung

Für alle von C0 durch Schritte erreichbaren Schnitte füge einen neuen Zustand hinzu und beschrifte ihn.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

14

Diplom-verteidigung

Transitionssystem




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0

14

Diplom-verteidigung

Transitionssystem

sC0




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0

14

Diplom-verteidigung

Transitionssystem

sC0




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1

14

Diplom-verteidigung

Transitionssystem

sC0sC1




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1

14

Diplom-verteidigung

Transitionssystem

sC0sC1

sC2




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

14

Diplom-verteidigung

Transitionssystem

sC0sC1

sC2


Wiederhole dies für alle Abläufe von !.



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem

! Zustandsübergänge:


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem


Jeder Schritt erfüllt Klauselmenge A von Next.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem


Jeder Schritt erfüllt Klauselmenge A von Next.Beschrifte Zustandsübergänge mit "i ("i $ A).


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

15

Diplom-verteidigung

Transitionssystem



Wiederhole dies für alle Abläufe von !.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

sC0sC1

sC2

rp

0

rr

rd

§

rp rd rp

rc rr

1 0 1

…

…

…

C0 C1 C2

16

Diplom-verteidigung

Formale Fundierung

Eigenschaften von TS!:

! Für alle Abläufe von !, für alle Schnitte C, die mit Schritten erreichbar sind, existiert ein erreichbarer entsprechender Zustand sC in TS!.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

16

Diplom-verteidigung

Formale Fundierung

Eigenschaften von TS!:

! Für alle Abläufe von !, für alle Schnitte C, die mit Schritten erreichbar sind, existiert ein erreichbarer entsprechender Zustand sC in TS!.

! Für alle erreichbaren Zustände sC in TS!

existiert ein Ablauf von ! mit einem entsprechenden Schnitt C, der mit Schritten erreichbar ist.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

17

Diplom-verteidigung

Formale Fundierung

Können wir alle Schnitte mit Schrittenvon C0 aus erreichen?


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd rp t rd rp

u rc rr

1 0 1

…

…

…

! u1 ! u2 ! u3 ! !

§

C0 C1 C2 C3"*

17

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd rp t rd rp

u rc rr

1 0 1

…

…

…

! u1 ! u2 ! u3 ! !

§

C0 C1 C2 C* C3"*

17

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd rp t rd rp

u rc rr

1 0 1

…

…

…

! u1 ! u2 ! u3 ! !

§

C0 C1 C2 C* C3"*

17

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd rp t rd rp

u rc rr

1 0 1

…

…

…

! u1 ! u2 ! u3 ! !§

C0 C1 C2 C* C3"*

17

Diplom-verteidigung

Formale Fundierung

Können wir alle Schnitte mit Schrittenvon C0 aus erreichen? "


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd rp t rd rp

u rc rr

1 0 1

…

…

…

! u1 ! u2 ! u3 ! !§

C0 C1 C2 C* C3"*

18

Diplom-verteidigung

Formale Fundierung

Gilt #$ !? Nicht notwendigerweise!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

18

Diplom-verteidigung

Formale Fundierung

Gilt #$ !?

Es gilt jedoch stets für umgebungs-invariante Formeln.

Nicht notwendigerweise!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

18

Diplom-verteidigung

Formale Fundierung

Gilt #$ !?




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

18

Diplom-verteidigung

Formale Fundierung

Gilt #$ !?


Kann wörtlich verstanden werden:



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

18

Diplom-verteidigung

Formale Fundierung

Gilt #$ !?


Kann wörtlich verstanden werden:

Eine Formel ! ist umgebungsinvariant gdw. für alle Abläufe # mit # ! gilt:Wenn #$ auf den Systemvariablen mit # übereinstimmt, dann gilt #$ !.



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

19

Diplom-verteidigung

Formale Fundierung

Eigenschaften von TS! (! umgebungs-invariant):

! Für alle Abläufe von !, für jeden Schnitt C, der mit Schritten erreichbar ist, existiert ein erreichbarer entsprechender Zustand sC in TS!.




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

19

Diplom-verteidigung

Formale Fundierung






Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

19

Diplom-verteidigung

Formale Fundierung






Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

20

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

20

Diplom-verteidigung

Formale Fundierung


1. Jeder Schnitt entspricht einem Zustand.

2. Jeder Ablauf entspricht Interleavings.

3. Jeder Zustand entspricht einem Schnitt.

4. Jedes Interleaving entspricht einem Ablauf.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

20

Diplom-verteidigung

Formale Fundierung






Die Interleavings von ! sind Pfade in TS!.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

20

Diplom-verteidigung

Formale Fundierung






Die Interleavings von ! sind Pfade in TS!.

% TS! ist eine TLDA-Interleavingsemantik.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

21

Diplom-verteidigung

Formale Fundierung

! Zusammenhangzwischen Abläufenund Interleavings


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0 C1

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0 C1 C2

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0 C1 C2 C3

21

Diplom-verteidigung

Formale Fundierung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

rp

0

rr

rd

§

rp rd

rc

1 0

…

…

…

C0 C1 C2 C3

Produce

Deliver&Filling

Remove&Emptying

22

Diplom-verteidigung

Formale Fundierung

! Transitionssystemerlaubt explizitesModelchecking.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

22

Diplom-verteidigung

Formale Fundierung


! Ziel weiterer Arbeit:Entwicklung vonModelchecking-Algorithmen


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

22

Diplom-verteidigung

Formale Fundierung


! Ziel weiterer Arbeit:Entwicklung vonModelchecking-Algorithmen

! Beispiel: Gilt die Formel ?


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

23

Diplom-verteidigung

E!zientere Algorithmen

! Problem: Klauselanzahl der DNF kann exponentiell steigen!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

23

Diplom-verteidigung



! Meist sind mehr als 99 % der Klauseln widersprüchlich!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

23

Diplom-verteidigung



! Meist sind mehr als 99 % der Klauseln widersprüchlich!

! Beispiel: Die DNF des Produzenten-/Konsumentensystemes besteht aus 16875 Klauseln, von denen jedoch nur 26 für das Transitionssystem wesentlich sind.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

24

Diplom-verteidigung


! Die disjunktive Normalform muss nicht vollständig gebildet werden!


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

24

Diplom-verteidigung




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

24

Diplom-verteidigung



! kompositionaler Aufbau von Spezifikationen:


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

24

Diplom-verteidigung



! kompositionaler Aufbau von Spezifikationen:

! Idee: nur DNF der Komponenten bilden


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

25

Diplom-verteidigung

E!zientere Implementierung

25

Diplom-verteidigung


Klausel

25

Diplom-verteidigung


Klausel Komponente

25

Diplom-verteidigung


Klausel KomponenteStartknoten Endknoten

25

Diplom-verteidigung


! DNF-Graph

! Pfade entsprechen Klauseln der Gesamtspezifikation

25

Diplom-verteidigung


! DNF-Graph

! Pfade entsprechen Klauseln der Gesamtspezifikation

26

Diplom-verteidigung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

……

Klauseln der Komponente i Klauseln der Komponente i+1

26

Diplom-verteidigung


! Beschriebener Pfad ist widersprüchlich


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

……


26

Diplom-verteidigung




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

……


26

Diplom-verteidigung




Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

……


27

Diplom-verteidigung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

27

Diplom-verteidigung



Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

! On-the-fly-Verfahren:

1. Widerspruch erkannt

2. Klausel austauschen

3. Pfad fortsetzen

28

Diplom-verteidigung


! On-the-fly-Verfahren:! Berechnung kann früher abgebrochen

werden! nicht alle Klauseln müssen betrachtet

werden! weniger Speicherplatz notwendig


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

28

Diplom-verteidigung


! On-the-fly-Verfahren:! Berechnung kann früher abgebrochen

werden! nicht alle Klauseln müssen betrachtet

werden! weniger Speicherplatz notwendig

! Beispiel:! Nur 1407 von 16875 Klauseln müssen

analysiert werden.! DNF-Graph hat nur 30 Knoten.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

29

Diplom-verteidigung


! ~-Variablen sind oft Grund für Widersprüchlichkeit

! kann oft nicht rein syntaktisch erkannt werden:


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

29

Diplom-verteidigung




! Regeln, um Informationen zu gewinnen:1. Zerlegung:

2. Transitivität:3. Erweiterung:


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

29

Diplom-verteidigung




! Regeln, um Informationen zu gewinnen:1. Zerlegung:

2. Transitivität:3. Erweiterung:

! Regeln basieren auf Mengenbeziehungen


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

30

Diplom-verteidigung


w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

30

Diplom-verteidigung


! ~-Graph

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

30

Diplom-verteidigung


! ~-Graph

! jeder Knoten entspricht einer ~-Variable

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

30

Diplom-verteidigung


! ~-Graph

! jeder Knoten entspricht einer ~-Variable

! Kanten entsprechen Mengenbeziehungen

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

31

Diplom-verteidigung


! Informationsgewinnung:! Gegeben:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yzKonsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

31

Diplom-verteidigung


! Informationsgewinnung:! Gegeben:

! Berechnet:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yzKonsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

32

Diplom-verteidigung


! Erkennung von Widersprüchen:! Gegeben:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yzKonsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

32

Diplom-verteidigung



! Berechnet:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yzKonsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

32

Diplom-verteidigung



! Berechnet:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz

wyz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

32

Diplom-verteidigung



! Berechnet:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yz

wyz


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

Widerspruch!

33

Diplom-verteidigung


! Minimale Repräsentation

! Repräsentanten:

w x y z

wx wy wz xy xz

wxy wxz wyz xyz

wxyz

yzKonsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

34

Diplom-verteidigung


! ~-Graph:! e!zientes Verfahren zur Erkennung von

Widersprüchen! Datenstruktur zur minimalen

Repräsentation von Informationen Konsumenten-/Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

34

Diplom-verteidigung


! ~-Graph:! e!zientes Verfahren zur Erkennung von

Widersprüchen! Datenstruktur zur minimalen

Repräsentation von Informationen

! Beispiel:! Beim Konsumenten-/Produzentensystem

konnten so alleine 577 widersprüchliche Klauseln entdeckt werden.

! Minimale Repräsentation spart 57 % Speicherplatz.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

35

Diplom-verteidigung

Ausblick

! Für kleine Beispiele sind die entwickelten Algorithmen sehr e!zient.


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

35

Diplom-verteidigung

Ausblick


! Komplexität der DNF wurde nicht verringert Konsumenten-/

Produzentensystem

Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

35

Diplom-verteidigung

Ausblick


! Komplexität der DNF wurde nicht verringert

! Anzahl der ~-Variablen steigt ebenfalls exponentiell


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

35

Diplom-verteidigung

Ausblick


! Komplexität der DNF wurde nicht verringert

! Anzahl der ~-Variablen steigt ebenfalls exponentiell

! Analyse der Aktionen (Preprocessing!) kann Stunden dauern


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

36

Diplom-verteidigung

Ausblick

! alternative Spezifikationsmöglichkeiten! Aktionen direkt angeben


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

36

Diplom-verteidigung

Ausblick

! alternative Spezifikationsmöglichkeiten! Aktionen direkt angeben

! alternativen Verifikationsmöglichkeiten:! symbolisches Modelchecking (SAT)! Theorembeweiser


Einführungin TLDA

Semantiken

Transitionssystem

FormaleFundierung


Ausblick

01/04/11

Formale Fundierung und e!zientere Implementierung der schrittbasierten TLDA-

Interleavingsemantik

Vielen Dank!

Niels Lohmann

[email protected]://www.informatik.hu-berlin.de/~nlohmann/studium

Education

Formale Fundierung und effizientere Implementierung der schrittbasierten TLDA-Interleavingsemantik