Beweisgraphen

Seminar: Analyse von PetrinetzmodellenWS 2007/08

Dozent: Peter Massuthe

Vortrag: Mike Herzog

Humboldt Universität zu BerlinInstitut für Informatik

2

Beweisgraphen - aber wozu?Beweisgraphen - aber wozu?

• Betrachten Verhalten von Petrinetzen

• Normalerweise Modelchecking

• Häufig Formeln der Form G(p→Fq)

• Mit Beweisgraphen effizienter möglich

3

Beweisgraphen - BeispielBeweisgraphen - Beispiel

c d

••

eb a

A B

C D

E

N2 =

Beweisgraph für N2 ⊨ A ↦ E

A E

AB

AD

c

dCD e

BECBde?

AE

c

e?

4

• gerichteter Graph G (genauer: „Netzwerk“) mit je einer ausgezeichneten Quelle p und einer Senke q

• Knoten sind Zustandsformeln in N

• Kantenbeschriftungen sind Transitionen in N

• enthält min 1 Pfad von p nach q

• kreisfrei, zusammenhängend

• bildet Halbordnungsrelation

• Für jeden Knoten r mit den Nachfolgern r1, r2, r3, ...gilt: r (↦ r1 r2 r3 ...)

Beweisgraphen - EigenschaftenBeweisgraphen - Eigenschaften

5

Leads-to FormelnLeads-to Formeln

Zustandsformeln p

Sagen– M ⊨ p („die Markierung M erfüllt p“), gdw. M(p) ≥ 1

– w ⊨ p ↦ q („der Ablauf w erfüllt p leads-to q“), gdw.Zu jedem i mit Mi ⊨ p existiert ein j mit j ≥ i und Mj ⊨ q

– N ⊨ p ↦ q („das Netz N erfüllt p leads-to q“), gdw.Jeder Ablauf w des Netzes gilt w ⊨ p ↦ q

A Cc

6

Leads-to Formeln - BeispieleLeads-to Formeln - Beispiele

N2 ⊨ A ↦ C

N2 ⊨ AB ↦ CD

N2 ⊨ A ↦ E

N2 ⊨ D ↦ D

¬AB ↦ AD

c d

••

eb a

A B

C D

E

N2 =

7

Effekt einer Transition auf eine Markierung - Beispiel

Effekt einer Transition auf eine Markierung - Beispiel

Teilmarkierung– Wissen oft nicht über gesamtes Netz Bescheid.– Ist unter Umständen nicht nötig.

„Effekt von t auf L“ am Beispiel– eff(AB, d) = D– eff(AB, e) = AE

•

•d

e

A

B

C

D

E

8

Effekt einer Transition auf eine Markierung - Definition

Effekt einer Transition auf eine Markierung - Definition

Definition: Sei N = (P,T,F) ein Netz, sei t T und sei L eine Markierung. Dann ist die Markierungeff(L, t) := max(L(p) + t(p), 0)der Effekt von t auf L.

Lemma: Sei N = (P,T,F) ein Netz, sei t T, seiM ―t→ M‘ ein Schritt von N und sei L ≤ M. Dann gilt:

1. eff(L, t) ≤ M‘.

2. Falls L = M, gilt eff(L, t) = M‘

9

Die Pick-up Regel - IdeeDie Pick-up Regel - Idee

Lemma: N ⊨ t ↦ Vu(t) eff(t, u)

N ⊨ AB ↦ D AE

N ⊨ d ↦ eff(d, d) eff(d, e)

•

•d

e

A

B

C

D

E

10

Die Pick-up Regel - ErweitertDie Pick-up Regel - Erweitert

Lemma: N ⊨ t ↦ Vu(t) eff(t, u)

AC ↦ ... nicht mit Lemma ableitbar,da für kein t gilt AC = t.

Es gilt aber dennochN ⊨ AC ↦ (CD CE AF)

Beobachtung:AC ist „progress prone“

•

•

e

f

A

B

C

D

F

d

E

11

Die Pick-up Regel - AllgemeinerDie Pick-up Regel - Allgemeiner

Lemma: N ⊨ t ↦ Vu(t) eff(t, u)

Allgemeineres Lemma: Sei N = (P, T, F) ein Netz, sei Q P progress prone. Dann giltN ⊨ Q ↦ VuQ eff(Q, u).

•

•

e

f

A

B

C

D

F

d

E

12

Die Pick-up Regel - BeispielDie Pick-up Regel - Beispiel

Allgemeineres Lemma: N ⊨ Q ↦ VuQ eff(Q, u)

N ⊨ Q ↦ VuQ eff(Q, u) mit Q = {AC}

N ⊨ AC ↦ VuAC eff(AC, u) mit AC = {d, e, f}

N ⊨ AC ↦ eff(AC, d) eff(AC, e) eff(AC, f)

N ⊨ AC ↦ CD CE AF•

•

e

f

A

B

C

D

F

d

E

13

Die Pick-up Regel - (cont.)Die Pick-up Regel - (cont.)

d

•

b e

f

A

B

C

D

E

F

Nach Lemma: BC ↦ E BF.

Wissen aber, dass BC → ¬D.

Lösung: lösche„verhinderte Transitionen“

aus Q

Allgemeineres Lemma: N ⊨ Q ↦ VuQ eff(Q, u)

N12=

14

Die Pick-up RegelDie Pick-up Regel

Gegeben: Sei N = (P, T, F, M0) ein Netz, sei Q P.

Gesucht: N ⊨ Q ↦ ...

Lösung:• Aktiviert Q eine Transition?

(Wenn nicht, ist keine Formel ableitbar.)• Setze U := Q• Nach belieben: Wenn Q die Transition t verhindert,

entferne t aus U

• Es gilt: N ⊨ Q ↦ uU eff(Q, u)

15

Beweisgraphen - Ende 1.TeilBeweisgraphen - Ende 1.Teil

A E

AB

AD

c

dCD e

BECBde?

AE

c

e?

c d

••

eb a

A B

C D

E

N2 =

Beweisgraph für N2 ⊨ A ↦ E

16

Cache RefreshingCache Refreshing

Beweisgraphen: kreisfreie, gerichtete Graphen mit ausgezeichneter Quelle und Senke

Leads-to Formeln: N ⊨ p ↦ q

Effekt einer Transition auf eine Markierung

Die Pick-up Regel: N ⊨ Q ↦ uU eff(Q, u)

Streichen verhinderter Transitionen aus U

•

•d

e

A

B

C

D

E

17

FairnessFairness

A• aa bb

•

cc dd

B C

D

E

N16 =

Beobachtung:

Alle Transitionensind konflikt-reduziert.

Wenn eine -Transition unendlich oft aktiviert ist,

wird sie irgendwann feuern.

18

Konflikt-reduzierte TransitionenKonflikt-reduzierte Transitionen

Definition: Sei N ein Petrinetz,sei t eine Transition von N.t ist konflikt-reduziert, wenn es höchstens einen Platz p in t gibt, für den gilt: { t } p.

p ist dann der Konflikt-Platz von t. bb

•

B

D

19

Fairness - (cont.)Fairness - (cont.)

N16 ⊨ A ↦ C

Zu zeigen: B BD,↦denn wegen der Fairness-Annahme für b wird bei der

(Teil-) Markierung BD die Transition b dann auch (irgendwann) feuern.

A B BE BD Ca c b

20

Beweistechnik IBeweistechnik I

A• aa

•cc

bb

C

DB

N19 = N19 ⊨ AB ↦ CD ist nicht durch stures Anwenden der Pick-up Regel beweisbar.

„Manchmal muß[!] man Information wegschmeißen“ W.R.

AB CA CDa b

CB

21

Beweistechnik IIBeweistechnik II

aa

•

cc

bb

C

B

A

N20 =

•D E

N20 ⊨ AD ↦ C ist nicht mit Standard-Beweisgraphen beweisbar.

Lösung:

Konstruieren uns die Invariante D+E = 1.

AD AB C

a

c ab

c?

BE AE

CDa

CE C

22

Wechselseitiger AusschlussWechselseitiger Ausschluss

N21 =

q

•

q

•

•

pendingL pendingR

criticalL criticalR

quietL quietR

1. Jeder kann jederzeit von quiet nach pending.

2. Wer pending ist, kommt irgendwann nach critical.

3. Es ist immer höchstens einer critical.

BeweisgraphenBeweisgraphen

23

• q

•

quiet pending

avail

silent

waiting

critical

•q

•

requested

granted

pending quiet

avail

silent

waiting

critical

24

• q

•

quiet pending

avail

silent

waiting

critical

requested

granted

25

FN22 ⊨ A ↦ E• q

•

A

C

D

E

•q

•

L R

M

N

P

Q

B G H

J K

ca b

d

f

e

h

k

j

m

n

g

26

BFNR

ABNR BFLN

ABLNENR

ELN

BFGP

ABGP

CFKP

EGP

ACKP CFQ

DHKP ACQ CFMR

DHQ ACMR CFLM

DHMR ACLM

DHLM

DJNR

DJLN

DJGP

27

F

• q

•

A

C

D

E

•q

•

L R

M

N

P

Q

B G H

J K

ca b

d

f

e

h

k

j

m

n

g

N22 ⊨ A ↦ E

28

F

• q

•

A

C

D

E

•q

•

L R

M

N

P

Q

B G H

J K

ca b

d

f

e

h

k

j

m

n

g

• q

• q

•

N22 ⊨ A ↦ E

29

N22 ⊨ H ↦ HM

H HQHK HKP m HMk

N22 ⊨ A ↦ E

A JAB JDACc? b H HMs.o. j d Ea

Beweisgraph für N22 ⊨ A ↦ EBeweisgraph für N22 ⊨ A ↦ E

30

Streichen verhinderter TransitionenStreichen verhinderter Transitionen

N22 ⊨ A ↦ E

A JAB JDACc? b H HMs.o. j d Ea

BH

b?

BHM

BHQ

BHK

BAH

BFH

m

j BJ

EH

ACK

ABJ

b

N22 ⊨ H ↦ HM

31

Beweisgraphen - ZusammenfassungBeweisgraphen -

Zusammenfassung

Beweisgraph

Leads-to Formel

Teilmarkierung

Pick-up Regel

verhinderte Transition

Fairness

konflikt-reduzierte Transition