Petrinetze - informatik.uni-augsburg.de · Inhaltsverzeichnis 0 Literatur 2 1 Einführung 3 2 Grundbegriffe 7 3 S- und T-Invarianten 22 4 Einige Entscheidbarkeitsprobleme 27 5 Beschränktheit

Prof. Dr. W. VoglerInstitut fur InformatikUniversitat Augsburg

Petrinetze

Inhaltsverzeichnis

0 Literatur 2

1 Einfuhrung 3

2 Grundbegriffe 7

3 S- und T -Invarianten 22

4 Einige Entscheidbarkeitsprobleme 27

5 Beschranktheit und Uberdeckbarkeit 31

6 Strukturtheorie und Free-Choice-Netze 37

7 Netzvariationen 427.1 High-level-Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427.2 Netze mit Zeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.3 Netze mit Prioritaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.4 Netze mit Inhibitor-Kanten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.5 Vergleich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.6 Kapazitaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

8 Nichtdeterminismus und modulare Konstruktion 51

Kapitel 0

Literatur

Baumgarten: Petri-Netze. Grundlagen und Anwendungen. BI-Wissenschaftsverlag, 1990Desel, Reisig, Rozenberg (eds.): Lectures on Concurrency and Petri Nets. Advances inPetri Nets. Springer, LNCS 3098, 2004Peterson: Petri Net Theory and the Modelling of Systems. Prentice Hall, 1981Priese, Wimmel: Theoretische Informatik - Petrinetze. Springer, 2003Reisig: Petrinetze - Modellierungstechnik, Analysemethoden, Fallstudien. Vieweg + Teub-ner, 2010Reisig, Rozenberg (eds.): Lectures on Petri Nets I: Basic Models und II: Applications.Springer, LNCS 1491 und 1492, 1998Starke: Analyse von Petri-Netz-Modellen. Teubner, 1990[Vogler: Modular Construction and Partial Order Semantics of Petri Nets. Springer, LNCS625, 1992]

Kapitel 1

Einfuhrung

Petrinetze sind formale Modelle (des Informations- bzw. Kontrollflusses) nebenlaufiger Sy-steme.

• formales Modell: mathematisches Abbild eines geplanten oder existierenden Systems

– exakt (= verbal)

– Verstandnis (geeignete Abstraktion)

– Testen (falls System geplant oder storanfallig)

– Analyse, Verifikation

Eine Modellklasse soll ausdrucksstark sein, d.h. zu moglichst vielen Systemen soll einmoglichst adaquates Modell existieren. (gewisser Konflikt zu Verstandnis und Analy-sierbarkeit; s. Automaten und formale Sprachen)

• a) von Neumann-Maschine:

Ablauf = Folge von Zustanden und Ubergangen

Programm = Berechnung einer Funktion ⇒ Ablauf soll endlich sein

b) nebenlaufiges (paralleles, verteiltes) System:

Vorgange nebeneinander her (z.B. Großrechner+I/O-Gerate+Benutzer, Rechner-netzwerke, Fabrik, Buro, Mensch, . . . )

– verschiedene Komponenten

∗ lokale Zustande

∗ Synchronisation, Konfliktauflosung, Verklemmung

– Aktivitaten wichtig (“Jede Nachricht wird irgendwann empfangen”, “Variable xwird nie von zwei Personen zugleich beschrieben”)

– evtl. unendliche Ablaufe

Beispiel: Ein Produzent sendet Objekte uber einen Puffer der Kapazitat 1 an einen Ver-braucher:

KAPITEL 1. EINFUHRUNG 4

a) Zustandsorientiertes Modell: A1 und A2 fuhren s synchron aus; A2 und A3 fuhren esynchron aus; vgl. Abb. 1.1.

p s s e e v

3 endliche Automaten

fp

fs

leer

voll fe

fv

f=fertig zu

p=produzieren

s=senden

e=empfangen

v=verbrauchen

Abbildung 1.1:

Problem: 3 Modelle statt einem; Text

b) Ereignisorientiertes Modell: Prozeßalgebren wie CCS, TCSP, ACPdefinierende Gleichungen; rechte Seite ist ∼ regularer Ausdruck

PROD = p.s.PROD

BUFF = s.e.BUFF

CONS = e.v.CONS

SY STEM =(

PROD‖{s}BUFF)

‖{e}CONS

c) Petrinetze: (vgl. Abb. 1.2)

fp

fs

voll

leer

fe

fv

s ep v Npc1

Abbildung 1.2:

• Reprasentation von Ereignissen und lokalen Zustanden

• graphisch


• diskret

• unstrukturiert im Vergleich zu b)

− nachteilig bei Entwurf/Analyse

+ homogenes operationales Modell

+ verschiedene Strukturierung moglich: A1‖A2‖A3 oder auch Abb. 1.3Die Komponenten in Abb. 1.3 beschreiben eine Sendung und eine Bestatigung/An-forderung; • steht fur ein Objekt, eine Nachricht oder eine gultige Bedingung.

fs

voll

fv

fp

leer

fe

p

p

s

s

e

e

v

v

Abbildung 1.3:

Erweiterungen:

• auf Puffer mit unbegrenzter Kapazitat (vgl. Abb. 1.4)

• Objekte paarweise empfangen (vgl. Abb. 1.5)

Ziele der Vorlesung uber Petrinetze:

• Anwendungsrelevanz

• interessante mathematische Theorie (gewisser Widerspruch zu “Anwendung”)

• Vorbereitung auf Literatur (“uberflussige” Randbemerkungen)

• Meine Sicht


fp

fs

fe

fv

Puffer

p e vs Npc

Abbildung 1.4:

2

fp

fs

fe

fv

p s e v

Abbildung 1.5:

Hier haben wir nur den Kontrollfluss modelliert; man kann statt schwarzer Marken auchObjekte/Daten verwenden, wobei beim Schalten z.B. die Daten bearbeitet werden; vgl. Ka-pitel 7.

Kapitel 2

Grundbegriffe

Definition 2.1 Ein Netzgraph ist ein gerichteter, kantengewichteter paarer (bipartiter)Graph (S, T,W ), wobei S und T disjunkte endliche Mengen sind und W : S×T ∪T ×S 7→ N(inkl. 0); Kantenmenge F = {(x, y) |W (x, y) 6= 0}.

Bemerkung: Im Prinzip laßt sich fast alles auf unendliche Netze erweitern.

Darstellung und Bezeichnungen

t ∈ T Transition �

s ∈ S Stelle, Platz ©(x, y) ∈ F Kante (F=Flußrelation) PfeilW GewichtsfunktionW (x, y) Kantengewicht Ist W (x, y) = n > 1, wird der Pfeil mit n beschriftet.

Sei x ∈ S ∪ T . Dann ist •x = {y | (y, x) ∈ F} der Vorbereich von x und x• ={y | (x, y) ∈ F} der Nachbereich von x. Fur X ⊆ S∪T ist •X = {y | ∃x ∈ X : (y, x) ∈ F} undX• = {y | ∃x ∈ X : (x, y) ∈ F}.

x heißt isoliert, falls •x ∪ x• = ∅. x heißt vorwarts- (ruckwarts-) verzweigt, falls |x•| ≥ 2( |•x| ≥ 2). Ist s ∈ S vorwarts-verzweigt, deutet dies einen Konflikt an. x, y ∈ S ∪ T bildeneine Schlinge, falls (x, y), (y, x) ∈ F .

Transitionen reprasentieren Aktivitaten, Stellen sind lokale Zustande. Welche Zustande“gelten”, wird durch eine Markierung M : S 7→ N ausgedruckt. Eine Markierung konnen wirz.B. als Vektor angeben, der fur jede Stelle eine Komponente hat.

Fur Funktionen und die entsprechenden Vektoren sind in gleicher Weise Multiplikationmit Skalaren sowie (argument- bzw. komponentenweise) Addition und ≤ (eine Halbordnung!)etc. definiert; das werden wir u.a. in der Schaltregel (s.u.) nutzen.

s ∈ S bzw. S′ ⊆ S heißen unmarkiert unter M , falls M(s) = 0 bzw. M(s′) = 0∀s′ ∈ S′,andernfalls markiert unter M .

Ein Petrinetz (oder Netz, S/T -Netz, P/T -Netz) N = (S, T,W,MN ) besteht aus

• einem Netzgraphen (S, T,W )

• einer Anfangsmarkierung MN

KAPITEL 2. GRUNDBEGRIFFE 8

z. B. M(s)=2 oder M(s)=n n

Abbildung 2.1:

Darstellung: s. Abb. 2.1Zu N gehoren immer S, T,W ; zu N ′ gehoren immer S′, T ′,W ′ etc.Im Zweifel: SN , TN ,WN , immer: MN ✷

Definition 2.2 t ∈ T ist aktiviert unter der Markierung M , M [t〉, falls ∀s ∈ S : W (s, t) ≤M(s) ; andere Notation: t− ≤ M , wobei t− die Funktion S 7→ N, s 7→ W (s, t) sei. (aquivalent:∀s ∈ •t : W (s, t) ≤ M(s) ) (vgl. Abb. 2.2).

Analog wird t+ uber W (t, s) definiert. ✷

2

3

3 2

N1 N2

N3 N4

Abbildung 2.2:

N1 : . . . M [t〉N2 : . . . M [t〉N3 : . . . M [t〉N4 : . . . M [t〉

Falls M [t〉, so kann t schalten, und die Folgemarkierung M ′ entsteht, M [t〉M ′, fallsM ′ = M + t+ − t−; andere Notationen dafur sind M ′ = M + ∆t, wobei ∆t : S 7→ Z,s 7→ W (t, s)−W (s, t) der feste Veranderungsvektor von t ist, bzw.

M ′(s) =

M(s)−W (s, t) , falls s ∈ •t− t•

, falls s ∈ t• − •t

, falls s ∈ •t ∩ t•

, falls s /∈ •t ∪ t•


3

2

3

2

2

Abbildung 2.3:

Die Folgemarkierungen fur N3 und N4 aus Abb. 2.2 sind in Abb. 2.3 gezeigt, wobei ∆t(−2,−1, 0, 1) bzw. (−1, 0, 3) ist. Wir haben also MN3

[t〉M mit M = MN3+∆t = (3, 1, 2, 1)+

(−2,−1, 0, 1) = (1, 0, 2, 2).

Erweiterung auf Folgen

Definition 2.3 Sei w ∈ T ∗ (wobei wir λ fur die leere Folge schreiben), dann gilt M [w〉 (bzw.M [w〉M ′), falls w = λ (und M = M ′) oder w = w′t mit t ∈ T , M [w′〉M ′′[t〉 (und M ′′[t〉M ′).

FS(N) = {w ∈ T ∗ |MN [w〉} ist die Menge der Schaltfolgen von N (firing sequence). M ′

heißt erreichbar von M , M ′ ∈ [M〉, falls w ∈ T ∗ existiert mit M [w〉M ′. [MN 〉 ist die Mengeder in N erreichbaren Markierungen bzw. die Erreichbarkeitsmenge von N .

w ∈ Tω ist eine unendliche Schaltfolge, falls alle endlichen Prafixe von w Schaltfolgensind. ✷

Bemerkung: w = t1t2 . . . ist (un)endliche Schaltfolge ⇔ Es gibt Markierungen M1, M2, . . .mit MN [t1〉M1[t2〉M2 . . .

Beispiel: [MNpc〉 ⊇ {(1, 0, n, 1, 0) |n ∈ N} (vgl. Abb. 1.4) Beweis mit Induktion uber n

Definition 2.4 Der Erreichbarkeitsgraph R(N) (reachability graph) ist der kantenbeschrifte-te gerichtete Graph ([MN 〉, {(M, t,M ′) |M [t〉M ′} ,MN ), wobei (M, t,M ′) eine Kante von Mnach M ′ mit Beschriftung t und MN eine ausgezeichnete Ecke (Startecke) ist. ✷

Beispiel: Abb. 2.4. Andere Notationen fur die Anfangsmarkierung sind hier {fp, leer, fe}bzw. fp+ leer + fe, s.u. Multimengen.

Beobachtung: s passiert erst und unmittelbar nach p; also muss es im Netz

Aufbau des Erreichbarkeitsgraphen: A = {MN}, V = E = ∅;solange A nicht-leer: verschiebe M von A nach V und fuge fur alle t ∈ T – falls M [t〉M ′ –die entsprechende Kante zu E hinzu, sowie M ′ zu A, falls M ′ 6∈ V ∪A.

Vgl. Info III:

Beispiel: Wieviele erreichbare Markierungen hat das Netz in Abb. 2.5 bei n Kreisen?

Zustandsexplosion!! (state explosion)


p

s

ep

e

s

p

v

p v

v

v

(1,0,0,1,1,0)

(0,1,0,1,1,0)

(1,0,1,0,1,0)

(0,1,1,0,1,0)

(0,1,0,1,0,1)

(1,0,0,1,0,1)

(1,0,1,0,0,1)

(0,1,1,0,0,1)

p s e v

Abbildung 2.4:

Abbildung 2.5:


M [t1 . . . tn〉M′ =⇒ M ′ = M +

n∑

i=1∆ti

M ′ hangt also nur vom Parikh-Bild von t1 . . . tn ab:

Definition 2.5 Sei w ∈ A∗. Dann ist Parikh(w) : A 7→ N definiert durch Parikh(w)(a) =Anzahl der a in w. ✷

Proposition 2.6 M [w〉M ′ =⇒ M ′ = M +∑

t∈T

Parikh(w)(t) ·∆t

Proposition 2.7 Seien M , M1, M2 Markierungen, w ∈ T ∗ und M1[w〉M2. Dann gilt M +M1[w〉M +M2.

Beweis: Intuition: Die zusatzlichen Marken, die M beschreibt, werden von w offenbar nichtbenotigt; sie bleiben also unberuhrt liegen.

Ein formaler Beweis (der vor allem fur weniger einsichtige Aussagen gebraucht wird) mußsich auf Definition 2.3 stutzen; also:

Induktion uber die Lange von w (dabei lasst man den eingeklammerten Text ublicherweiseweg):

(|w| = 0, also) w = λ ⇒ M1 = M2 ⇒ (M1 +M)[λ〉(M2 +M)

(Induktionsvoraussetzung: Ist |w| = n, so gilt fur alle MarkierungenM ,M1,M2:M1[w〉M2

=⇒ M +M1[w〉M +M2

Induktionsschritt: Sei M1[w〉M2 mit |w| = n+1, also) w = w′t und M1[w′〉M ′

1[t〉M2.Nach Ind.vor. (M1 +M)[w′〉(M ′

1 +M), und wir mussen zeigen, daß t jetzt aktiviert ist, unddie Folgemarkierung bestimmen:

a) M ′1[t〉 ⇔ M ′

1 ≥ t− ⇒ M ′1 +M ≥ t− ⇒ (M ′

1 +M)[t〉. Zusatzliche Marken storen also nicht.

b) M ′1[t〉M2 ⇒ M2 = M ′

1+∆t ⇒ M2+M = M ′1+M+∆t ⇒ (mit a)) (M ′

1+M)[t〉(M2+M).Zusatzliche Marken bleiben also unberuhrt liegen.

⇒ (M1 +M)[w′〉(M ′1 +M)[t〉(M2 +M). �


Satz 2.8 N ′ entstehe aus N durch

1. Erhohen der Anfangsmarkierung, also MN ′ = MN + ∆M fur eine Markierung ∆M ;dann ist

2. Weglassen einer Stelle s0, also S′ = S − {s0} und MN ′ = MN |S−{s0} etc.; dann ist

3. Weglassen einer Transition t0, also MN ′ = MN , T ′ = T − {t0}; dann ist


Aussagen uber FS(N)

Definition 2.9 Sei L ⊆ A∗. Dann ist Pref(L) = {v | ∃w ∈ L : v ist ein Prafix von w}. Lheißt prafix-abgeschlossen, falls L = Pref(L). ✷

Proposition 2.10 a) Fur alle Netze N ist FS(N) prafix-abgeschlossen.

b) Ist [MN 〉 endlich, so ist FS(N) regular.

Beweis:a) klar.b) �

Beispiel: L = {λ, b, a, aa, aab} ist prafix-abgeschlossen und endlich (also regular), aber nichtFS(N) fur irgendein N . Denn sonst: MN ≥ b− ∧MN + 2∆a ≥ b− =⇒ MN +∆a ≥ b− =⇒MN [ab〉 =⇒ WIDERSPRUCH!

Fazit: Die Umkehrung von 2.10 gilt i.a. nicht; Netze haben so gesehen eine beschrankteAussdrucksstarke. Zur Abhilfe:

Definition 2.11 Ein beschriftetes Petrinetz N = (S, T,W,MN , l) besteht aus einem Netz(S, T,W,MN ) und einer Transitionsbeschriftung (labelling) l : T 7→ Σ ∪ {λ}, wobei Σ eineMenge von Aktionen ist; l(t) = λ ⇒ t intern, unsichtbar.

Schaltregel fur Aktionen: M [t〉M ′ ⇒ M [l(t)〉〉M ′; analog M [l(t)〉〉 Aktionsschaltfolgen (Interne Transitionen verschwinden auf der Aktionsebene!)

L(N) = {v ∈ Σ∗ |MN [v〉〉}: Sprache von N ✷

Beispiel: Erweitern der Pufferkapazitat von Npc1 auf 2: s. Abb. 2.6 bis 2.8. In Abb. 2.7 giltMN [psps〉〉, wobei der Puffer eine Kapazitat von mindestens 2 demonstriert; dabei entsprechendie beiden p derselben Transition, die beiden s aber verschiedenen Transitionen. Analog ergibtMN [t1t2t1t3t2〉 in Abb. 2.8 auch fur dieses Netz MN [psps〉〉.

Abbildung 2.6:


Abbildung 2.7:

Abbildung 2.8:

Die Netze in 2.7 und 2.8 sind sicher (s.u.); sichere Netze sind so etwas wie verteilte endlicheAutomaten. Das Netz in 2.7

Definition 2.12 Ein beschriftetes Netz N = (S, T,W,MN , l, F in) mit Endmarkierung ist einbeschriftetes Netz (S, T,W,MN , l) zusammen mit einer endlichen Menge Fin ⊆ M(S) vonMarkierungen. Die Sprache Lfin(N) ist {v ∈ Σ∗ | ∃M ∈ Fin : MN [v〉〉M}. Lλ ist die Klassedieser Sprachen, L fur die Netze ohne interne Transitionen. ✷

Beispiel: Abb. 2.9 zeigt ein Netz mit Fin = {(0, 0, 1)} und Lfin =

λ

a b

s1 s

s2

3

t1

t 2

t 3

Abbildung 2.9:


Wir erhalten einen (nicht immer endlichen) Automaten zu Lfin, wenn wir in R(N) dieZustande in Fin zu Endzustande machen und jede Kante (M, t,M ′) durch . . . . . . ersetzen.

Satz 2.13 L enthalt alle regularen Sprachen.

Beweis:Betrachte endliche Automaten als Netz:

• Zustande Stellen

• Anfangszustand enthalt eine einzige Marke

• Kanten Transitionen mit |•t| = |t•| = 1 und beschriftet wie die jeweilige Kante

• Endzustand q q (als Multimenge) in Fin �


Nebenlaufigkeit I

p

e

"diamond", Karo Hinweis auf p, e nebenläufig

Aber:

gemeinsame Ressource

p e p e

e

p

Abbildung 2.10:

Nur auf der linken Seite gilt MN [(

pe

)

〉; mit einer zusatzlichen Marke”vor“ p gilt sogar

MN [(

2pe

)

〉.

Definition 2.14 Eine Multimenge µ uber X ist eine Funktion µ : X 7→ N; µ ∈ M(X). Damitsind auch fur Multimengen Multiplikation mit Skalaren sowie (argumentweise) Addition und≤ etc. definiert, also auch maximale Multimengen in einer Menge von Multimengen. Wiridentifizieren:

• ∅ mit µ ≡ 0, d. h. µ(X) = {0}

• Y ⊆ X mit µY , wobei µY (x) =

{

1 fur x ∈ Y

0 sonst(”Menge als Bitvektor“)

• x ∈ X mit µx, wobei µx(y) =

{

1 fur y = x

0 sonst

Notation: Sehen wir x und x′ als Multimengen ist auch x + 2x′ eine, die also x auf 1,x′ auf 2 und alles andere auf 0 abbildet; alternativ:

(

x2x′

)

. Wir schreiben auch x ∈ µ, fallsµ(x) ≥ 1. ✷

Jetzt gilt allgemein X+∅ = X; fur Mengen X,Y mit Y ⊆ X gilt aber i.A. nicht X+Y =X. Wie hangt fur Mengen X,Y X + Y mit X ∪ Y und X ∩ Y zusammen?

Definition 2.15 Ein Schritt µ ist eine nichtleere Multimenge uber T . µ ist aktiviert unterM , M [µ〉, fallsDie Summe ist eine Linearkombination der Vektoren t−.

Falls M [µ〉, so kann µ schalten, wobei die Folgemarkierung M ′ entsteht, M [µ〉M ′,falls .

Erweiterung auf Folgen wie in 2.3; SS(N) = {w ∈ (M(T ) \ {∅})∗ |MN [w〉} ist die Mengeder Schrittschaltfolgen (step sequences). Zwei Transitionen t, t′ sind nebenlaufig unter M , fallsM [t + t′〉. Zwei verschiedene Transitionen t, t′ sind in Konflikt unter M , falls M [t〉, M [t′〉,aber ¬M [t+ t′〉. ✷


2

2

5

2

t

t'

t''

Abbildung 2.11:

In Abb. 2.11 gilt: MN [(

t2t′

)

〉, ¬MN [(

t′

t′′

)

〉, ¬MN [(

t3t′

)

〉 Unter den vonMN aktivierten Schrit-ten sind maximal:

Im Beispiel von Abb. 2.10: MN1[(

pe

)

〉, ¬MN2[(

pe

)

〉. Also sind p und e nebenlaufig (oderunabhangig) in N1, aber in Konflikt in N2.

Fur beschriftete Netze kann man das Verhalten auf Aktionsebene”liften“:

M [µ〉M ′ ⇒ M [l(µ)〉〉M ′; l(µ) Multimenge von Aktionen – dabei λ-Transitionen loschensowie auch Schritte nur aus λ-Transitionen (solche Schritte entsprechen λ)

Aktionsschrittfolgen.

Proposition 2.16 Sei M [ti〉, i = 1, . . . , n, fur verschiedene ti und die •ti seien paarweisedisjunkt. Dann gilt M [(t1 + . . .+ tn)〉

Beweis: Angenommen ∃s :∑n

i=1W (s, ti) > M(s); dann gibt es ein j mit s ∈ •tj, und furalle i 6= j ist dann s 6∈ •ti, d.h. W (s, ti) = 0. Also: W (s, tj) =

∑ni=1 W (s, ti) > M(s) und

¬M [tj〉, ein Widerspruch. �

Man kann also nebenlaufige Transitionen zu einem gewissen Grad graphisch erkennen.

Proposition 2.17 Sei M [µ〉M ′ und w ∈ T ∗ mit Parikh(w) = µ. Dann gilt M [w〉M ′.

In Worten: Jede Linearisierung eines schaltbaren Schrittes kann schalten und fuhrt zurselben Folgemarkierung.

Uber Schrittfolgen werden also dieselben Markierungen erreicht wie uber Schaltfolgen;eine entsprechende Variante SR(N) des Erreichbarkeitsgraphen hat also dieselben Ecken,aber mehr Kanten. (Bsp.: In Abb. 2.10 gibt es beim linken Netz . . . .)

Die Umkehrung zu 2.17, also”Kann jede Linearisierung eines Schrittes schalten, so ist

auch der Schritt schaltbar“ gilt nicht, vgl. Abb. 2.12 und(

ab

)

.

a b

Abbildung 2.12:

Aber:


Satz 2.18 Sei N schlingenfrei und µ ein Schritt, so daß ∀w ∈ T ∗ : Parikh(w) = µ =⇒M [w〉. Dann gilt M [µ〉.

Beweis: Annahme: ¬M [µ〉, d. h. ∃s ∈ S mit∑

t∈Tµ(t) · t−(s) > M(s).

Wahle w1, w2 ∈ T ∗ mit Parikh(w1w2) = µ, w1 ∈ (s•)∗ und w2 ∈ (T − s•)∗. ∀t ∈ s• gilt:

• Parikh(w1)(t) = µ(t)

• ∆t(s) = −t−(s) (nach Vorauss.)

Sei M [w1〉M1[w2〉.Dann: 0 ≤ M1(s) = M(s) +

∑

t∈s•Parikh(w1)(t) ·∆t(s) = (wegen bullets)

M(s)−∑

t∈s•µ(t) · t−(s) = (Def. s•) M(s)−

∑

t∈Tµ(t) · t−(s) =⇒ WIDERSPRUCH! �

Fur schlingenfreies N gilt also:

• “Karo” in R(N) ⇐⇒ 2er-Schritt

• “Wurfel” in R(N) ⇐⇒ 3er-Schritt etc.

Beispiel zu 2.16, 2.17 und 2.18: Npc1 aus Abbildung 1.2 bzw. 2.4; wieviele “Karos” und“Wurfel” hat R(Npc1)?

Geben Sie eine Schrittfolge mit vier jeweils maximalen Schritten an!


Erreichbarkeit

(E) Erreichbarkeitsproblem: Gegeben ein Netz N und eine Markierung M . Ist M erreich-bar in N?Z.B. Lfin(N) 6= ∅ ⇔ ∃M ∈ Fin : M erreichbar in N .

(0-E) 0-Erreichbarkeitsproblem: Gegeben N . Ist die 0-Markierung erreichbar?

Diese Probleme kann man durch Aufbau des Erreichbarkeitsgraphen losen – wenn dieserendlich ist! Selbst dann sind die Probleme sehr schwer (vgl. Kapitel 4), da er sehr groß seinkann.

Definition 2.19 Eine Stelle s heißt n-beschrankt, falls fur alle erreichbaren MarkierungenM gilt: M(s) ≤ n. s heißt beschrankt, falls es ein solches n gibt. N heißt (n-)beschrankt, fallsalle Stellen (n-)beschrankt sind. 1-beschrankte Netze heißen sichere Netze. ✷

Bemerkung: Ist N beschrankt, dann gibt es ein n, so daß N n-beschrankt ist. Gilt nichtfur unendliche Netze.

Abbildung 2.13:

Proposition 2.20 Fur jedes Netz N gilt: [MN 〉 endlich ⇐⇒ N beschrankt.

Beweis:“=⇒”: N ist n-beschrankt fur n =“⇐=”: Ist N n-beschrankt, so gilt |[MN 〉| ≤ �


Verklemmung

Beispiel: Die speisenden Philosophen (Dijkstra)Funf Philosophen sitzen an einem runden Tisch und denken und essen. Zwischen je zwei

Philosophen liegt eine Gabel; zum Essen sind jeweils zwei Gabeln notig, s. Abb. 2.14 bzw.Abb. 2.15.

Gesamtstruktur:

Abbildung 2.14:

Abbildung 2.15:

Problem:Abb. 2.16 zeigt eine Losung.

Abbildung 2.16:

Ißt jeder Philosoph immer wieder? Z.B. nicht bei der Schaltfolge t+1 t−1 ; ”

in Wirklichkeit“kann jetzt jeder Philsosoph essen, d.h. t+1 t

−1 ist ein Artefakt; wir mussen maximale Schalt-

folgen (bzgl. Prafix) betrachten, die unendlich sind oder in einer toten Markierung enden,s.u.

Weitere Probleme: Schaltfolge (t+1 t−1 )

ω; auch diese unendliche Schaltfolge entsteht ausfalscher Sichtweise – sie verletzt die schwache Fairneß, da t+3 standig aktiviert ist.

Schaltfolge (t+1 t−1 t

+3 t

−3 )

ω; diese verletzt die starke Fairneß, da t+2 unendlich oft aktiviertist. Es ist plausibel, daß t+2 daher

”in Wirklichkeit“ auch einmal schalten wird.

. . . hungert t+2 aus. (Naheres in den Ubungen)

Verklemmung: keine Transition kann schalten.partielle Verklemmung: eine Transition ist tot.

Definition 2.21 t heißt tot unter M , falls ∀M ′ ∈ [M〉 : ¬M ′[t〉; t heißt tot, falls t tot unterMN .M heißt tot, falls alle Transitionen tot unter M sind; N heißt tot, falls MN tot ist. N heißtverklemmungsfrei, falls keine tote Markierung erreichbar ist.

t heißt lebendig unter M , falls t unter keiner von M erreichbaren Markierung M ′ tot ist:. . . t heißt lebendig, falls t lebendig unter MN .M heißt lebendig, wenn alle t unter M lebendig sind. N heißt lebendig, falls MN lebendig ist,d.h. alle Transitionen lebendig sind. ✷


(L) Lebendigkeitsproblem: Gegeben N . Ist N lebendig?(EL) Einzellebendigkeitsproblem: Gegeben N und t ∈ T . Ist t lebendig?

Kapitel 3

S- und T -Invarianten

Reader-Writer-Problem: s. Abb. 3.1

3 Prozesse wollen wiederholt lesend auf eine Datei zugreifen.2 Prozesse wollen wiederholt schreibend auf diese Datei zugreifen.Wenn ein Prozeß schreibt, soll kein anderer lesen oder schreiben.

3

2 3

Zugriffsrechte z

s-passiv

willschreiben

will lesen

l-passivt

t

t

t

t

t1

2

3

4

5

6

s=schreibend l=lesend3

3

Abbildung 3.1: das Netz Nrw

Eigentlich sind Vektoren hier immer Spaltenvektoren; wir schreiben trotzdem statt MTNrw

einfach MNrw= (2, 0, 0, 3, 3, 0, 0).

Beh: ∀M ∈ [MNrw〉 : M(s) 6= 0 =⇒ M(s) = 1 ∧M(l) = 0

Zugriffsrechte liegen auf z, l oder konzentriert in einer Marke auf s, also:

Beh: ∀M ∈ [MNrw〉 : 3 ·M(s) +M(z) +M(l) = 3.

Mit anderen Worten, die gewichtete Markierung ist immer 3, wobei y1 = (0, 0, 3, 1, 0, 0, 1)die Gewichtung angibt; z.B. gilt yT1 ·MNrw

= 3. Damit folgt die erste Beh.

Beweis: Die Behauptung gilt unter MNrw. Ferner:

KAPITEL 3. S- UND T -INVARIANTEN 23

Effekt von t1: 0 0 0 = 0Effekt von t2: 3 -3 0 = 0Effekt von t3: -3 3 0 = 0Effekt von t4: 0 0 0 = 0Effekt von t5: 0 -1 1 = 0Effekt von t6: 0 1 -1 = 0 �

Definition 3.1 Die Inzidenzmatrix eines Netzes N ist (C(N)(s, t))s∈S,t∈T mit C(N)(s, t) =∆t(s) (Spalten von C(N) sind die ∆t).

Faßt man t ∈ T als Schritt und damit als (Spalten-)Vektor auf, ist also ∆t = C(N) · t.(Gemaß Definition 2.14 steht t auch fur µt.) Ist M [t〉M ′, so gilt M ′ = M + C(N) · t; giltM [w〉M ′, so ist M ′ = M+C(N) ·Parikh(w). (Einbettung in Lineare Algebra; dies entsprichtProp. 2.6)

✷

Bei einer Gewichtung y wie im Beispiel soll yT · M ′ = yT · M gelten; dies wird durchyT · C(N) = 0T gewahrleistet.

Definition 3.2 Eine S-Invariante y : S 7−→ Z ist eine Losung von C(N)T · y = 0.Der Trager einer S-Invariante y ist {s ∈ S | y(s) 6= 0}.N heißt von S-Invarianten uberdeckt, wenn N eine positive S-Invariante besitzt. (positiv:

alle y(s) > 0) ✷

Bemerkung: Falls es zu jedem s ∈ S eine nicht-negative S-Invariante (nicht-negativ: alley(s) ≥ 0) gibt, deren Trager s enthalt, so enthalt die Vereinigung dieser Trager S, d.h. jedess und damit S bzw. N wird von diesen Tragern uberdeckt.

Da die S-Invarianten unter Addition (und Multiplikation mit ganzzahligen Skalaren) ab-geschlossen sind (s.u.), gibt es dann eine positive S-Invariante.

Satz 3.3 Ist y eine S-Invariante, dann gilt fur alle M ∈ [MN 〉 : yT ·M = yT ·MN .

Beweis: s.o., d.h.: ∃w : MN [w〉M ; also yT · M = yT · (MN + C(N) · Parikh(w)) =yT ·MN + yT · C(N) · Parikh(w) = yT ·MN �

Bemerkung: Notwendige Bedingung fur Erreichbarkeit.

Satz 3.4 Ist keine Transition in N tot (oder N gar lebendig) und y ein ganzzahliger Vektormit yT ·M = yT ·MN fur alle M ∈ [MN 〉, dann ist y eine S-Invariante.

Beweis:∀t ∈ T ∃M ∈ [MN 〉 : M [t〉M ′; ferner ist yT ·M = yT ·MN = yT ·M ′ = yT ·M + yT ·∆t.

Da die ∆t die Spalten von C(N) sind, gilt also yT · C(N) = 0T . �

Im obigen Beispiel hat Nrw die folgenden S-Invarianten:


sp ws s z lp wl ly1 = ( 0, 0, 3, 1, 0, 0, 1 )y2 = ( 1, 1, 1, 0, 0, 0, 0 )y3 = ( 0, 0, 0, 0, 1, 1, 1 )

... und daher auch z.B. y1 + y2 (wg. C(N)T · (y1 + y2) = C(N)T · y1 + C(N)T · y2 = 0)und 3 · y1.

Beachte, daß wir zur Angabe der S-Invarianten im ublichen Vektor-Stil die Stellen belie-big, aber einheitlich geordnet haben; ebenso sollte man zusatzlich die Transitionen ordnen,um die Inzidenzmatrix im ublichen Stil anzugeben.

Oft ist der Trager einer S-Invariante relativ klein; gemaß unserer Notation fur Multimen-gen (=Vektoren) konnen wir daher z.B. y1 gunstig als 3s+z+ l schreiben. Im Zusammenhangmit S-Invarianten wollen wir diese Notation auch auf negative Koeffizienten erweitern, alsoauch so etwas wie 3s− z + l schreiben.

Um zu prufen, daß ein y tatsachlich eine S-Invariante ist, genugt es offensichtlich, dieTransitionen zu betrachten, die dem Trager von y benachbart sind; wir vereinbaren, daßwir als Beleg fur y fur jede solche Transition t ihren gewichteten Effekt fur die Stellen sdes Tragers auflisten wollen (also jeweils y(s)∆t(s)). Der Beleg fur y1 ist also: t2 : 3,−3, 0;t3 : −3, 3, 0; t5 . . . Dabei soll die Reihenfolge der Stellen im Zweifel durch die Notation derS-Invariante (hier also 3s+z+ l) festgelegt werden. Schließlich wollen wir die mit y gewichteteAnfangsmarkierung yT ·MN das Anfangsgewicht von y nennen; fur y1 ist es also 3. Damit istder Beweis fur die erste Beh. oben: y1 ist S-Invariante mit Anfangsgewicht 3.

Nach Satz 3.3 gilt also ∀M ∈ [MN 〉 : 3M(s) + M(z) + M(l) = 3; dafur wollen wirkurz 3s + z + l = 3 schreiben. Mit dieser Notation kann man rechnen: Wir haben auchsp+ws+s = 2 (∀M ∈ [MN 〉 : M(sp)+M(ws)+M(s) = 2) und damit sp+ws+4s+z+l = 5(∀M ∈ [MN 〉 : M(sp) +M(ws) + 4M(s) +M(z) +M(l) = 5) sowie 2s+ z + l− sp−ws = 1etc.

S-Invarianten sind nach Definition ganzzahlige Losungen eines homogen linearen Glei-chungssystems. Sie lassen sich aber oft auch durch Einsicht in das System oder

”durch

Hinschauen“ finden. Im obigen Beispiel Nrw bleibt die Zahl der Schreibprozesse offenbarkonstant, und diese befinden sich in den Zustanden sp, ws oder s; daher muß eigentlichy2 = sp + ws + s eine S-Invariante mit Anfangsgewicht 2 sein. Man kann auch einfach ver-suchen, eine S-Invariante zu finden, die sp mit 1 gewichtet; wegen t1 mussen wir dann wshinzufugen; wegen t2 ist es dann am einfachsten (besonders wenn die S-Invariante nicht-negativ sein soll) auch s hinzufugen, und wir sind fertig. Alternativ konnte man naturlichauch −z wahlen und mußte dann auf 3sp+ 3ws erhohen etc.

Satz 3.5 Ist s ∈ S und y eine nicht-negative S-Invariante mit y(s) > 0, dann ist s – auchbei geanderter Anfangsmarkierung M0 – beschrankt. Ist yT · M0 = 1, so ist s sicher unterM0.

Beweis:Bei beliebiger Anfangsmarkierung M0 und M ∈ [M0〉 gilt y(s) ·M(s) ≤ yT ·M = yT ·M0,

also M(s) ≤ yT ·M0

y(s) . �

Definition 3.6 Ein Netz heißt strukturell beschrankt, wenn es bei beliebig geanderter An-fangsmarkierung stets beschrankt ist. ✷

Korollar 3.7 Ist N von S-Invarianten uberdeckt, so ist es strukturell beschrankt.


Bemerkung: Besitzt N eine lebendige Markierung, so gilt die Umkehrung; s. Starke.

Wegen Korollar 3.7 ist Nrw also strukturell beschrankt. Außerdem konnen wir mit Hilfeder S-Invarianten zeigen, daß Nrw lebendig ist. Dazu zwei Begriffe: Ein home state ist eineMarkierung, die von jeder erreichbaren Markierung erreichbar ist; ein Netz ist reversibel, wenndie Anfangsmarkierung ein home state ist.

Da von MNrwaus keine Transition tot ist, genugt es zu zeigen, daß Nrw reversibel ist. Sei

also M ∈ [MNrw〉 beliebig:

• Durch Schalten von t3 und t6 lassen sich s und l leeren;

• wegen y1 sind jetzt drei Marken auf z; durch Schalten von t2t3 bzw. t5t6 lassen sichzusatzlich ws und wl leeren;

• wegen y2 sind jetzt zwei Marken auf sp;

• wegen y3 sind jetzt drei Marken auf lp.

Dies ist eine ubersichtliche Argumentation fur alle erreichbaren Markierungen ohne auf-wendige Erzeugung des Erreichbarkeitsgraphen.

NS-Inv

s

s

s

ss

1

2

3

4

51

2

3

4

t

t t

t

Abbildung 3.2:

NS−Inv in Abb. 3.2 ist lebendig und sicher, aber nicht von S-Invarianten uberdeckt. Furjede S-Invariante y ist y(s1) = y(s2) wegen t4, also y(s5) = 0 wegen t2.

Ubung: Durch welche Anfangsmarkierung und Schaltfolgen wird eine Stelle unbeschrankt?

Definition 3.8 Eine T -Invariante x : T 7−→ Z ist eine Losung von C(N) · x = 0. N heißtvon T -Invarianten uberdeckt, wenn es eine positive T -Invariante gibt. ✷

Proposition 3.9 Sei w ∈ T ∗ mit M [w〉M ′. Dann: Parikh(w) ist eine T -Invariante ⇐⇒M = M ′.


Beweis:M ′ = M + C(N) · Parikh(w). �

Satz 3.10 Wenn N bei einer Anfangsmarkierung M0 lebendig und beschrankt ist, dann istN von T -Invarianten uberdeckt.

Beweis:Da N lebendig ist, gibt es eine Schaltfolge w1 mitM0[w1〉M1, die alle Transitionen enthalt.

Entsprechend gibt es w2 mit M1[w2〉M2 und allen Transitionen etc. Da N beschrankt ist, gibtes i < j mit Mi = Mj . Dann gilt Mi[wi+1wi+2 . . . wj〉Mj = Mi, und Parikh(wi+1 . . . wj) isteine positive T -Invariante wegen 3.9. �

Von”gutartigen“ Netzen wird oft erwartet, daß sie lebendig und beschrankt sind; ist also

N nicht von T -Invarianten uberdeckt (Lineare Algebra), so ist es nicht gutartig (operational).

Kapitel 4

Einige Entscheidbarkeitsprobleme

(E) Erreichbarkeitsproblem: Gegeben ein Netz N und eine Markierung M . Ist M erreich-bar in N?Z.B. Lfin(N) 6= ∅ ⇔ ∃M ∈ Fin : M erreichbar in N .

(0-E) 0-Erreichbarkeitsproblem: Gegeben N . Ist die 0-Markierung erreichbar?

(TE) Teilerreichbarkeitsproblem: Gegeben N , S′ ⊆ S und M ′ : S′ 7→ N. Gibt es eineerreichbare Markierung M mit M |S′ = M ′?Z.B. s, s′ sind kritische Bereiche paralleler Prozesse, z.B. Zugriff auf dieselbe Variable. Gibtes eine erreichbare Markierung M mit M(s) = M(s′) = 1?

Frage: Sind die obigen Probleme entscheidbar?

Definition 4.1 Ein Entscheidungsproblem D ist eine Ja/Nein-Frage, zu deren Beantwortungein Verfahren gesucht wird. Formal bestehtD aus einer Menge inst(D) von Fallen (instances),z.B. Menge der Netze, und der Antwort D : inst(D) → {T, F}, z.B. (0-E)(N) = T ⇐⇒ in Nist die 0-Markierung erreichbar.

Ein Entscheidungsverfahren fur D ist ein Algorithmus (z.B. ein C-Programm oder aucheine Turingmaschine), der bei jeder Eingabe aus inst(D) mit einer Antwort aus {T,F} haltund dabei die Funktion D berechnet.

Entscheidungsproblem A ist auf Entscheidungsproblem B (Turing-)reduzierbar, wenn einLosungsverfahren fur A existiert, das ein (gedachtes) Losungsverfahren fur B benutzt. (Manschreibt also eine Funktion, die A berechnet und eine Funktion fur B aufruft; das kann man,selbst wenn man eine solche Funktion fur B (noch) gar nicht hat. Letzteres ist ublich beimtop-down-Entwurf.)

A ist (linear, polynomiell) many-one-reduzierbar auf B, wenn ein (linearer, polynomiel-ler) Algorithmus existiert, der jeden Fall von A in einen Fall von B mit gleicher Antwort

umwandelt. Alin7−→M B, A

poly7−→M B. ✷

Bemerkung: Ist A auf B reduzierbar, so ist mit B auch A entscheidbar; ist A unentscheid-

bar, so auch B. Ist Alin7−→M B, so ist grob gesagt der Aufwand fur A großenordnungsmaßig

≤ dem Aufwand von B; (warum evtl. kleiner?) also: A schwer ⇒ B schwer.

Genauer: Ist Alin7−→M B und B in linearer Zeit entscheidbar, so auch A. Gilt Analoges,

wenn wir beide Male linear durch quadratisch oder durch polynomiell ersetzen?

KAPITEL 4. EINIGE ENTSCHEIDBARKEITSPROBLEME 28

Satz 4.2 (0-E)lin7−→M (E)

lin7−→M (TE)

lin7−→M (0-E)

Beweis:*** Sei N , S′, M ′ ein Fall von (TE). Konstruiere N wie in Abb. 4.1 in linearer Zeit. Ist

M ′ in N teil-erreichbar, so auch in N ; nachfolgendes Schalten der ts (M ′(s)-mal fur s ∈ S′)ergibt 0-Markierung.

Sei wtsw′ ∈ FS(N ); dann ist auch ww′ts ∈ FS(N ), da ts nur Marken entfernt. Erreicht

ein w die 0-Markierung in N , so auch ein w′w′′ mit w′ ∈ T ∗N , w′′ ∈ (TN \ TN )∗, wobei

w′ ∈ FS(N) die Teilmarkierung M ′ erreicht. �

��

s in S'

s' nicht in S'

N

t

ts

s'

M'(s)

ps

Abbildung 4.1:

Satz 4.3 (E) ist entscheidbar (also auch (0-E) und (TE)).

Beweis:Zu schwer [Mayr und (?) Kosaraju]; relativ einfache Darstellung in [Priese/Wimmel] �

Falls [MN 〉 endlich, laßt sich”leicht“ R(N) konstruieren und (E) etc. entscheiden.

Aber:

. . . . . . . . . n-mal

Abbildung 4.2:

N in Abb. 4.2 hat Große ≈ 9n, aber . . . erreichbare Markierungen! Zustandsexplosion!

(L) Lebendigkeitsproblem: Gegeben N . Ist N lebendig?(EL) Einzellebendigkeitsproblem: Gegeben N und t ∈ T . Ist t lebendig?

Satz 4.4 i) (L) ist reduzierbar auf (EL)

ii) (EL) ist reduzierbar auf (E)


iii) (0-E)lin7−→M Co-(L) (Co-A ist A mit umgekehrter Antwort.)

Beweis:

i) Lose (EL) fur

ii) Schwierig; die (Teil-) Markierungen, unter denen t tot ware, lassen sich bestimmen unddann auf Erreichbarkeit prufen.

iii) Sei N ein Fall von (0-E). Konstruiere N wie in Abb. 4.3 in linearer Zeit:

0-Markierung in N erreichbar ⇒ auch in N durch zusatzlich t2, und N ist tot.Sei 0-Markierung nicht erreichbar in N . Betrachte MN [w〉M .

i) w enthalt ein ts =⇒ t1 kann N fluten, d. h. keine Transition ist tot.

ii) sonst: w ∈ T ∗N ∪ T ∗

N t2V or.=⇒ ∃s ∈ SN : M(s) 6= 0 =⇒ ts kann schalten =⇒ i)

Also: 0-Markierung in N erreichbar ⇐⇒ N ist nicht lebendig. �

Satz 4.5 (L)lin7−→M (EL)

lin7−→M (L)

Beweis: Ubung �

Korollar 4.6 (L) und (EL) sind entscheidbar, aber”mindestens so schwer“ wie (E), (0-E)

und (TE).

Beweis: Satz 4.3 und 4.4 i) und ii) zeigen die Entscheidbarkeit. Satz 4.2 und 4.5 zeigen, daß(0-E), (E) und (TE) bzw. (EL) und (L) gleich schwer sind im Sinn von

”linear (many-one)

reduzierbar“. Fertig mit 4.4 iii). �


N

s

s2

s1

tst1

t2

Abbildung 4.3: s ist eine”typische“ Stelle von N ; jede solche Stelle bekommt eine eigene

Transition ts. Es gibt nur je ein s1, s2, t1 bzw. t2.

Kapitel 5

Beschranktheit und

Uberdeckbarkeit

Wir erinnern uns:Fur jedes Netz N gilt: [MN 〉 endlich ⇐⇒ N beschrankt.

s

1s

2s

3s

p

Abbildung 5.1:

In Abb. 5.1 ist (1, 0, 0) [ps〉 (1, 0, 1), also konnen wir die 3. Stelle “hochpumpen”, vgl. 2.7.Wir beschreiben diese Markierungen durch (1, 0, ω). Dabei steht ω fur

”beliebig groß“ – nicht

fur”unendlich“ oder

”beliebig“.

Definition 5.1 Eine erweiterte Markierung von N ist ein M : S 7→ N ∪ {ω}. ✷

Es ist n < ω, n+ω = ω+n = ω−n = ω fur n ∈ N, ω · 0 = 0 ·ω = 0 und n ·ω = ω ·n = ωfur n 6= 0.

Satz 5.2 N ist unbeschrankt ⇐⇒ ∃M,M ′ ∈ [MN 〉 und w ∈ T ∗ : M [w〉M ′ und M � M ′

(komponentenweise ≤, aber M 6= M ′)

Zum Beweis ein kleiner Ausflug:

Lemma 5.3 (Dicksons Lemma [Dickson 1913??])Sei (Mi)i∈N eine Folge von erweiterten Markierungen. Dann existiert eine (unendliche)

schwach monotone Teilfolge (Mij )j∈N, d.h. ∀j ∈ N gilt ij < ij+1 und Mij ≤ Mij+1.

Beweis:Sei S = {s1, . . . sn}. Wir konstruieren zunachst eine Teilfolge (Mij )j∈N, so daß

(Mij (s1))j∈N schwach monoton ist.

KAPITEL 5. BESCHRANKTHEIT UND UBERDECKBARKEIT 32

a) ∃k ∈ N ∪ {ω} ∃∞i : Mi(s1) = k. Wahle diese i als Teilfolge.

b) Sonst: Wahle i0 mit Mi0(s1) 6= ω.

Induktion: Ist ij bzw. Mij gewahlt, so gibt es ij+1 > ij mit Mij(s1) < Mij+1(s1) ∈ N;

andernfalls hatten die unendlich vielen Mi(s1) mit i > ij nur die endlich vielen Werte{ω} ∪ {0, . . . ,Mij (s1)} =⇒ WIDERSPRUCH zu b).

Dann wahlen wir aus dieser Teilfolge eine weitere, die zusatzlich schwach monoton fur s2ist etc. �

Definition 5.4 Ein Weg in einem gerichteten Graphen (V,E) ist eine Folge v1v2 . . . (vn)verschiedener vi ∈ V mit vivi+1 ∈ E; v1 . . . vn ist ein v1, vn-Weg. (V,E) ist lokal endlich, fallsfur jedes v ∈ V nur endlich viele v′ ∈ V mit vv′ ∈ E existieren. ✷

Satz 5.5 Konigs LemmaSei (V,E) ein unendlicher, lokal endlicher gerichteter Graph, so daß zu einem v0 ∈ V fur

alle v ∈ V ein v0, v-Weg existiert. Dann existiert ein unendlicher Weg v0v1 . . .

Beweis:Beh: ∃(vi)i∈N∀n ∈ N : ∃∞ Wege v0v1 . . . vnv

′ . . . v′′

Wir konstruieren die vi induktiv: n = 0: klar nach Voraussetzung, da V unendlich.Sei also v0 . . . vn konstruiert. Fur die unendlich vielen Wege v0 . . . vnv

′ . . . v′′ gibt es nurendlich viele v′, da (V,E) lokal endlich. Ein v′ tritt also unendlich oft auf; wahle vn+1 = v′,d.h. ∃∞ Wege: v0 . . . vnvn+1v

′′′ . . . v′′.Offenbar ist v0v1v2 . . . nun ein unendlicher Weg. �

Wir sind jetzt in der Lage, 5.2 zu beweisen:

Beweis: “=⇒”: Wegen 2.20 ist R(N) unendlich; alle M ∈ [MN 〉 sind von MN uber Wegeerreichbar; fur alle M gibt es hochstens |T | ausgehende Kanten. Wahle nach 5.5 einen un-endlichen Weg MN (= M0)M1M2 . . . Nach 5.3 gibt es Mi, Mj mit i < j und Mi ≤ Mj ; nachDefinition eines Weges gilt Mi 6= Mj , und das Wegstuck Mi . . .Mj entspricht einem w ∈ T ∗

mit Mi[w〉Mj .

“⇐=”: Wegen 2.7 gilt M [wn〉 fur alle n ∈ N, und s mit M(s) < M ′(s) ist unbeschrankt.�

Um ein unendliches R(N) endlich darzustellen, falten wir solche M und M ′ wie in 5.2zusammen; genauer: Ist M [w〉M ′[w〉M ′′, M � M ′, so falten wir M ′ und M ′′ zusammen zuM und setzen M(s) = ω, falls M(s) < M ′(s). In der Literatur finden sich verschiedeneVariationen des folgenden Algorithmus.


Algorithmus 5.6 (Uberdeckbarkeitsgraph Cov(N) = (V,E,MN ))

var V,A: Mengen von erweiterten Markierungen {A: aktuell}E: Menge von Kanten der Form (M, t,M ′) ∈ V × T × (V ∪A)V or: V ∪A 7→ V {Vorgangerfunktion}

beginV :=E:=∅; A:={MN}; V or(MN ):=NIL;while A 6= ∅ do

wahle M aus A; A:=A− {M}; V :=V ∪ {M};fur alle t ∈ T mit M [t〉 do

M ′:=M +∆t; (*) M∗:=M;

while M∗ 6= NIL und ¬M∗ ≤ M ′ do M∗:=V or(M∗) od;if M∗ 6= NIL then { M∗[w〉M ′ und M∗ ≤ M ′}

M ′:=M ′ + ω · (M ′ −M∗) fi { evtl. M∗ ∈ {M,M ′} }E:=E ∪ {(M, t,M ′)};if M ′ /∈ V ∪A then A:=A ∪ {M ′}; V or(M ′):=M fi

odod

end.

Bemerkung: Cov(N) ist nicht eindeutig, da M aus A frei gewahlt wird.

Beispiel: s. Abb. 5.2 und Abb. 5.3

s

1

t1

s

4 ts

5

t

2

s

2

s6

t' s7

t

3s

3

Abbildung 5.2:

Abbildung 5.3:

In Cov(N) finden sich: ttω1 isttω2 istt2t

′t3t3 ists1, s2, s3 zahlen t1, t2, t3. t1, t2 konnen unendlich oft schalten, t3 kann beliebig, aber nicht

unendlich oft schalten.s1 und s2, s2 und s3, aber nicht s1 und s3 konnen gleichzeitig jede Grenze uberschreiten.

Definition 5.7 Sei N ein Netz, und M1, M2 seien erweiterte Markierungen. M2 uberdecktM1, wenn M2 ≥ M1. M1 heißt uberdeckbar in N , wenn es ein M ∈ [MN 〉 gibt, das M1

uberdeckt.


Eine Menge S′ ⊆ S heißt simultan unbeschrankt, wenn es fur alle n ∈ N ein M ∈ [MN 〉gibt mitM(s) ≥ n ∀ s ∈ S′. Fur ein Cov(N) ist L(Cov(N)) die Menge aller w = t1 . . . tn ∈ T ∗

mit (MN , t1,M1)(M1, t2,M2) . . . (Mn−1, tn,Mn) in Cov(N); Mw := Mn. ✷

Bemerkung: Cov(N) ist endlicher (s.u.) Automat mit Startzustand MN und SpracheL(Cov(N)). Der Automat ist deterministisch, d.h. Mw ist wohldefiniert. Zusammenhang zwi-schen uberdeckbar und erreichbar?

Satz 5.8 Cov(N) ist endlich.

Beweis:Andernfalls betrachte zu Cov(N) = (V,E,MN ) den Graphen (Baum) (V,E′), fur den

MM ′ ∈ E′ ⇔ M = V or(M ′). Wie im Beweis zu 5.2 gibt es einen unendlichen Weg P in(V,E′) von MN aus und auf P eine schwach (sogar stark) monotone Sequenz (Mi)i∈N. WahleMj mit maximaler Anzahl von ω-Komponenten; also haben auf P alle M ab Mj dieselbenω-Komponenten. Nun gilt Mj � Mj+1, d.h. wir finden in 5.6 bei der Konstruktion von Mj+1

ein M∗ zwischen Mj (incl.) und Mj+1 mit M∗ � Mj+1. Da Mj , M∗ und Mj+1 dieselben

ω-Komponenten haben, gibt es also s ∈ S mit M∗(s) < Mj+1(s) ∈ N; nach 5.6 mußte alsoMj+1(s) = ω sein. =⇒ WIDERSPRUCH! �

Falls N beschrankt ist, ist Cov(N) = R(N); beim Auftreten der ersten ω-Komponentehatten wir namlich M∗[w〉M ′ mit M∗ � M ′ und wegen 5.2 ware N unbeschrankt. Cov(N)kann also sehr groß werden.

Korollar 5.9 Es ist entscheidbar, ob N beschrankt ist.

Beweis:Konstruiere Cov(N) und prufe auf ω-Komponenten. Tritt eine ω-Komponente auf, so ist

N unbeschrankt; s. o. Tritt keine auf, so generiert man gemaß 5.6 systematisch R(N) (vgl.Tiefen/Breitensuche), d.h. es ist Cov(N) = R(N) endlich, also ist N beschrankt. �

Was sagen uns die Markierungen in Cov(N) uber [MN 〉 bzw. L(Cov(N)) uber FS(N)?


Satz 5.10 i) Wenn MN [w〉M , dann ist w ∈ L(Cov(N)) und M ≤ Mw, genauer:

∀s ∈ S : M(s) = Mw(s) oder Mw(s) = ω.

ii) Wenn M uberdeckbar – oder speziell: erreichbar – in N ist, dann existiert eine erweiterteMarkierung in Cov(N), die M uberdeckt.

Beweis:

i) Induktiv uber |w|: w = λ: M = MN = Mλ

Sei nun MN [w〉M ′[t〉M , w ∈ L(Cov(N)) und M ′ ≤ Mw etc. Dann gilt: Mw[t〉, alsowt ∈ L(Cov(N)) und M = M ′ + ∆t ≤ Mw + ∆t ≤ Mwt; dabei gilt 6= nur fur ω-Komponenten.

ii) folgt aus i). �

Wir konnen aus”M in Cov(N)“ noch genauere Schlusse uber [MN 〉 ziehen.

Satz 5.11 Fur alle M in Cov(N) und alle n ∈ N gibt es ein M ′ ∈ [MN 〉, so daß

- M ′(s) = M(s), falls M(s) 6= ω

- M ′(s) > n sonst

Beweis:


Korollar 5.12 S′ ist simultan unbeschrankt ⇐⇒ ∃M in Cov(N) mit M(s) = ω ∀s ∈ S′.

Beweis:

“=⇒”: Definiere Mn durch Mn(s) =

{

n fur s ∈ S′

0 sonst. Nach Voraussetzung gibt es zu

jedem Mn ein uberdeckendes M ′n ∈ [MN 〉. Nach 5.10 ii) gibt es also ein uberdeckendes M ′′

n inCov(N). Unendlich viele dieser M ′′

n stimmen mit einem M uberein, da Cov(N) endlich ist.M erfullt die Behauptung.

“⇐=”: 5.11 �

Korollar 5.13 Eine Markierung M ist uberdeckbar in N ⇐⇒ M wird von einem M inCov(N) uberdeckt.

Beweis:“=⇒”: 5.10 ii)

“⇐=”: Setze n = max{

M(s) | s ∈ S}

und wende 5.11 auf M und n an. �

Korollar 5.14 t ist nicht tot in N ⇐⇒ t tritt als Kantenbeschriftung in Cov(N) auf.

Beweis:“=⇒”: 5.10 i)“⇐=”: Sei (M, t,M1) in Cov(N). Wende 5.11 auf M an mit n = max {t−(s) | s ∈ S} .

Fur M ′ gilt offenbar M ′[t〉 und M ′ ∈ [MN 〉. �

Wichtigster Inhalt dieses Kapitels: Beschranktheit ist entscheidbar. Der Uberdeckbarkeits-graph liefert ein entscheidbares hinreichendes Kriterium fur Nicht-Erreichbarkeit (Satz 5.10ii)) und Nicht-Schaltbarkeit im Sinn von 5.10 und des letzten Korollars.

Kapitel 6

Strukturtheorie und

Free-Choice-Netze

(vgl. Desel, Esparza: Free Choice Petri Nets. Cambridge University Press 1995)

Kap. 3: Netz-Struktur (algebraisch) – VerhaltenJetzt: graphentheoretische Struktur – Verhalten

Beispiel: In Abb. 6.1 gilt: Ist {s1, s2} geleert, bleibt es leer, und t ist tot. Ist {s3, s4}markiert, bleibt es markiert.

t

s s s s1 2 3 4

Abbildung 6.1:

Definition 6.1 R ⊆ S ist ein Siphon (deadlock, Tube), falls •R ⊆ R•. R ist eine Falle, fallsR• ⊆ •R. ✷

Im Bsp.: {s1, s2} bzw. {s3, s4}

Proposition 6.2 Ist R ein Siphon (Falle) und unmarkiert (markiert) unter M , so ist Rauch unmarkiert (markiert) unter allen M ′ ∈ [M〉.

Liegt im Bsp. eine zusatzliche Marke auf s3, so konnen wir analog zu S-Invarianten schrei-ben: s3 + s4 ≥ 1. Und auch damit kann man rechnen: Ware s4 + s5 eine S-Invariante mitAnfangsgewicht 2, also s4 + s5 = 2, so wurde auch gelten s3 + 2s4 + s5 ≥ 3.

Lemma 6.3 N habe keine isolierten Stellen, und R 6= ∅ sei ein Siphon. Dann ist R• 6= ∅.

KAPITEL 6. STRUKTURTHEORIE UND FREE-CHOICE-NETZE 38

Beweis: Sei s ∈ R. Falls s• 6= ∅, sind wir fertig. Falls s• = ∅, so gibt es t ∈ •s undt ∈ •R ⊆ R•. �

Satz 6.4 N habe keine isolierten Stellen. Ist R 6= ∅ ein Siphon und unmarkiert unterM ∈ [MN 〉, dann ist N nicht lebendig.

Beweis: Nach 6.3 gibt es t ∈ R•, und t ist tot unter M nach 6.2. �

Konvention: In diesem Kapitel sind im weiteren alle Kantengewichte 0 oder 1; s. Starkefur Erweiterungen.

Satz 6.5 Ist T 6= ∅ und M eine tote Markierung, dann ist R = {s ∈ S |M(s) = 0} einnichtleerer, unmarkierter Siphon.

Beweis: Sei t ∈ T . Da t tot ist, gibt es ein unmarkiertes s ∈ •t, d.h. R 6= ∅ und t ∈ R•. Alsoist •R ⊆ T = R•. �

Wie verhindern wir, daß ein Siphon geleert wird?

Satz 6.6 Sei T 6= ∅. Enthalt jeder nichtleere Siphon eine markierte Falle, dann ist N ver-klemmungsfrei.

Beweis: Angenommen, M sei eine erreichbare Markierung und N tot unter M . Dann istR = {s ∈ S |M(s) = 0} 6= ∅ ein Siphon wegen 6.5. Wegen 6.2 fur Fallen enthalt R keine unterMN markierte Falle =⇒ WIDERSPRUCH! �

Fur EFC-Netze laßt sich 6.6 zu einer Charakterisierung der Lebendigkeit ausbauen.

Definition 6.7 N ist ein Free-Choice-Netz (FC-Netz), falls ∀t, t′ ∈ T : t 6= t′ ∧ s ∈ •t ∩•t′ =⇒ •t = •t′ = {s}. N ist ein erweitertes Free-Choice-Netz (EFC-Netz), falls ∀t, t′ ∈ T :t 6= t′ ∧ •t ∩ •t′ 6= ∅ =⇒ •t = •t′. ✷

Beispiel: Das FC-Netz in Abb. 6.2 ist lebendig und sicher; es hat home-states, ist aber nichtreversibel.

Bemerkung 6.8 Sind N ein EFC-Netz, s ∈ S, t1, t2 ∈ s• und M eine Markierung, dannM [t1〉 ⇔ M [t2〉.

In FC- bzw. EFC-Netzen tritt keine Konfusion auf wie z.B. in Abb. 6.3.Hier wird der Konflikt zwischen t und t′ evtl. durch t′′ gelost, wobei t und t′′ nicht in

Konflikt stehen. (symmetrische Konfusion)In Abb. 6.4 ist t ist aktiviert, t′′ erzeugt unabhangig von t einen Konflikt zwischen t und

t′. (asymmetrische Konfusion) (s. Baumgarten fur genauere Definition)

Satz von Commoner: Sei N ein EFC-Netz ohne isolierte Stellen. N ist lebendig ⇐⇒Jeder nichtleere Siphon enthalt eine markierte Falle.

Wir skizzieren hier nur eine Richtung (”⇒“).

Lemma 6.9 1. Die Vereinigung von Siphons (Fallen) ist ein(e) Siphon (Falle).


Abbildung 6.2:

t t' t''

Abbildung 6.3:

2. Jedes R ⊆ S enthalt eine großte (d.h. eindeutige maximale) Falle.

3. R ⊆ S enthalt eine markierte Falle ⇐⇒ die großte Falle in R ist markiert.

Beweis:

1. Seien R1 und R2 Siphons; dann istAnalog fur Fallen.

2. ∅ ist eine Falle mit ∅ ⊆ R. Nach 1. ist

3. �


t''

t't

Abbildung 6.4:

Sei P = {s1 < · · · < sk} eine geordnete Teilmenge von Stellen eines Netzes N , d.h. dieElemente der Teilmenge erfullen s1 < s2 < · · · < sk fur eine willkurlich festgelegte Ordnung.Fur Markierungen M1 und M2 von N definieren wir die lexikographische Ordnung <P durch

M1 <P M2 ⇔ ∃i ≤ k :(

M1(si) < M2(si) ∧ ∀j = 1, . . . , i− 1 : M1(sj) = M2(sj))

In Worten: M1 ist kleiner M2 bzgl. <P , wenn sie auf einem”Anfangsstuck“ ubereinstimmen,

und an der ersten Stelle, an der sie sich unterscheiden, M1 kleiner als M2 ist.

Lemma 6.10 <P ist Noethersch (well founded), d.h. es gibt keine unendliche echt abstei-gende Kette (M1 >P M2 >P M3 . . . ).

Beweis: Ubung �

Lemma 6.11 Sei N ein EFC-Netz, R ⊆ S und Q die maximale (d.h. großte) Falle in R.Dann gibt es eine Ordnung P von R \ Q, so daß fur alle Markierungen M , unter denen Qunmarkiert ist, gilt:

[

(∃t ∈ R• : M [t〉) ∨ (R ist Siphon ∧ ∃t ∈ R• : t ist nicht tot unter M)]

=⇒[

∃M ′ ∈[M〉 : M ′ <P M und Q ist unmarkiert unter M ′

]


Beweis: Induktion uber n = |R\Q|. Fur n = 0 ist R = Q unmarkiert; daher ¬∃t ∈ R• : M [t〉und ggf. bleibt der unmarkierte Siphon R unmarkiert, d.h. alle t ∈ R• sind tot.

Fur n > 0 wahle r ∈ R\Q und tr ∈ r• mit t•r ∩R = ∅ – welche existieren, da R keine Falleist. (Und daher gibt es t ∈ R• \ •R und r ∈ •t ∩R; ware r ∈ Q, so ergabe t ∈ Q• ⊆ •Q ⊆ •Reinen Widerspruch.) Wahle nach Induktion eine geordnete Menge P ′ = {s1 < · · · < sn−1},die das Lemma fur R \ {r} erfullt, und setze P = {s1 < · · · < sn−1 < r}. Angenommen, Qist unmarkiert unter M .

1) Sei zunachst t ∈ R• mit M [t〉.a) t ∈ (R \ {r})•: Nach Induktion gibt es M ′ mit M ′ <P ′ M , so daß Q unmarkiert ist

unter M ′. Da r maximal ist in P , gilt dann aber auch M ′ <P M .b) Es sei a) verletzt, also t ∈ r•: Da N ein EFC-Netz ist, ist •t = •tr; damit gilt M [tr〉M

′,wobei M und M ′ gleich sind auf R\{r}, da a) verletzt ist (also •tr∩R = {r}) und t•r ∩R = ∅.Also ist M ′ <P M wegen tr ∈ r•, und Q ist auch unter M ′ unmarkiert.

2) Gelte nun: R ist Siphon ∧∃t ∈ R• : t ist nicht tot unter M . Wir konnen nun schalten,bis zum ersten Mal – unter M ′′ – ein solches t ∈ R• aktiviert ist. Da dabei keine Marke ausdem Siphon R entfernt wird, wird auch keine hinzugefugt; die Markierung auf R andert sichalso nicht, und wir konnen nun 1) anwenden. (M ′ <P M ′′ impliziert M ′ <P M , da M ′′ undM auf R gleich sind.) �

Beweis zum Satz von Commoner, HinrichtungUbung

Tip: Im Beweis wenden wir 6.11 nur fur den Fall an, daß R ein Siphon ist. (Warum wirdin dem Lemma auch uber allgemeines R geredet?)

Kapitel 7

Netzvariationen

7.1 High-level-Netze

Beschreibung von Daten, z.B. y := x+ 1 mit x, y ∈ N:

x = 0

y = 2

y = 1

y = 0

x = 1

.

.

. ...

.

.

.

.

.

.

Abbildung 7.1: y := x+ 1 ohne Kontrollfluss

Je x-Wert und je y-Wert gibt es eine Stelle, je Paar von Ausgangswerten fur x und y eineTransition, die den y-Wert gemaß Zuweisung abandert.

Netze werden evtl. unendlich; trotz regelmaßigen Aufbaus außerst unubersichtlich. ZurBehandlung von Daten und zur Ausnutzung von Symmetrien:

• Marken werden beschriftet (mit Variablenwerten, Nachrichten etc.);hier: mit Tupeln (Datensatz, Verbund/record/struct). Wir identifizieren jede Markemit ihrer Inschrift; jede Stelle wird entsprechend mit einem kartesischen Produkt alsTyp versehen, der die Marken auf dieser Stelle enthalt, z.B. Σ∗ × N fur (Name, Alter).Vgl. Abb. 7.2 sowie fur eine Verwendung von Paaren Abb. 7.3.

() identifizieren wir mit einer normalen Marke •; der Stellentyp entfallt.

• Kanten werden beschriftet, hier: mit Tupeln von Termen oder Multimengen solcherTupel; wertet man die Terme eines Tupels aus, ergibt sich ein Element des Typs der

KAPITEL 7. NETZVARIATIONEN 43

beteiligten Stelle.Terme sind aus Variablen, Konstanten und Funktionen bzw. Operationen aufgebaut;um Unklarheiten zu vermeiden, muss man die Variablen evtl. in den entsprechendenTransitionen deklarieren (x : N, y : {1, . . . , 5} o.a.).

Bei 1-Tupeln lassen wir evtl. die Klammern weg.

• Transitionen erhalten Anwendungsbedingungen; diese sind eine logische Beschreibungder operationalen Semantik, vgl. yneu = x+ 1 in Abb. 7.2.

x

x

y_neu

y_alt

1 0y =x+1neu

N N

Abbildung 7.2: y := x+ 1 mit Kontrollfluss

(x,y)

?

x < y

(x,y)

(x,y)

(y,x)≥x yN N×× N N ××

Abbildung 7.3: Paare sortieren

Das Netz in Abb. 7.2 bzw. in Abb. 7.6 unten ist eine Zusammenfaltung des Netzes in Abb.7.1 bzw. aus Kapitel 4.

Um eine Transition t zu schalten, muss man eine Belegung β der Variablen angeben, diein den Kanteninschriften

”an“ t auftreten. Eine solche Belegung nennen wir einen Modus von

t. Dabei ist t in einem Modus aktiviert, wenn

1. die Bedingungen in t unter der Belegung wahr werden;

2. ferner werten wir fur jedes s ∈ •t die entsprechende Kanteninschrift zu einer Multimengevon Marken aus – s muss dann entsprechende Marken in den geforderten Vielfachheitenenthalten.

Analog werden beim Schalten Marken im Nachbereich von t erzeugt. In Abb. 7.2 kann talso (genau) im Modus (1, 0, 2) schalten, d.h. mit x = 1, yalt = 0 und yneu = 2; Notation:MN [t(1, 0, 2)〉.

Abb. 7.4 zeigt, wie geeignete Kanteninschriften das Netz vereinfachen: alternativ konnteman 3 Variablen verwenden und in der Transition verlangen, dass diese denselbenWert haben.

Mit unseren Konventionen kann man das Netz aus Abb. 7.2 eleganter durch das Netz inAbb. 7.5 ersetzen.


x

x

?

N

N?

N

x

Abbildung 7.4:

x

x

x+1

y

1 0

N N

Abbildung 7.5: y := x+ 1 mit Kontrollfluss

In Abb. 7.6 gibt es z.B. die Schaltfolge t(ph1, g1) t′(ph1, g2) t(ph3, g3) t

′′(ph1, g1, g2); +in der Kanteninschrift ist hier das Multimengen-Plus. Ersetzt man in Abb. 7.3 (x, y) linksoben durch 2(x, y), werden geordnete Doubletten vereinfacht; setzt man 2(x, y) + (x′, y′) einund rechts oben (x + x′, y + y′), entfernt man zusatzlich ein beliebiges Paar und addiert eskomponentenweise auf die Ausgabe.

x x x x

y

(y)+(z)

x

essendePhilosophen

denkendePhilosophen

ph0

ph1ph2

ph3

ph4

x= phy= gj=i

ij

x= phy= gj=(i+1) mod 5

ij

g0

g2 g3

g4

g1

x= ph , y=g z=g , i=jk=(i+1) mod 5

i jk

x

y

Gabeln

Philosophenmit Gabel

Abbildung 7.6:

Achtung bei Kanten-Beschriftungen wegen Uberladung: 3x + y ist hier dasselbe wie(3x+ y), wahrend 3(x) + (y) eine Multimenge ist, die (x) dreimal und (y) einmal enthalt.Diese Konventionen sollen eine schlanke Notation erlauben; ein Problem stellt dabei z.B. 3(x+1) dar: Ist dies ein 1-Tupel ohne Außenklammern? Oder reprasentiert es drei Marken mit Wert


x+ 1? Im ersten Fall sollte man 3x+ 3 schreiben, so dass Klammern mit naturlichzahligemFaktor davor immer einem Tupel entsprechen.Ferner: 3 steht hier fur das normale Kantengewicht 3, d.h. fur 3(), oder fur (3), d.h. 3 ist einTerm; diese Falle kann man anhand des Stellentyps unterscheiden. Man kann auch ⊕ fur dieAddition von Multimengen schreiben.

Eine sinnvolle Ubersetzung eines Programms in ein HL-Netz erhalt die Struktur des Pro-gramms; sie ist lokal im folgenden Sinn und lasst sich daher durchfuhren, ohne das Programmvorher durchzuspielen. Letzteres ware zumindest sehr aufwendig und ist im Allgemeinen garnicht moglich (Halteproblem). Lokal bedeutet u.a., dass wie im Beispiel jeder Programmvaria-blen eine Stelle entspricht und jede Zuweisung eines Programms in eine Transition ubersetztwird; diese Transition beschafft sich uber die eingehenden Kanten die alten Variablenwer-te und schreibt uber die ausgehenden Kanten die neuen (veranderten oder unveranderten)Variablenwerte zuruck.

Da die Transitionen mit Bedingungen (z.B. in Pradikatenlogik erster Stufe) beschriftetsind, lassen sich ganz leicht in ahnlicher Weise Abfragen in Transitionen ubersetzen. Manch-mal ist es auch sinnvoll, eine Abfrage in die nachste Zuweisung zu integrieren.

Bemerkung: Man kann jedes HL-Netz zu einem HL-Netz mit einer Stelle und einerTransition zusammenfalten – aus Marke x auf Stelle s wird die Marke (x, s) auf der einzigenStelle. (Das ist wenig sinnvoll – wie man auch unstrukturiert, z.B. ohne Verwendung vonFunktionen/Prozeduren, programmieren kann.)

Man sollte fur die auftretenden Bedingungen bzw. Terme (wie x+y) eine geeignete Syntaxfinden; dann lassen sich auch furHL-Netze syntaktische S-Invarianten definieren. Andernfallskann man unrealistische Netze wie z.B. das in Abb. 7.7 definieren, bei dem < TM > eineTuringmaschine codiert.

x

x

< TM >

x hält auf

x hält nicht auf

hält

hält nicht

λ

λ

Abbildung 7.7:

7.2 Netze mit Zeit

Fur praktische Anwendungen spielt Zeit eine entscheidende Rolle. Dafur kann man z.B. furjede Transition t eine exakte Latenzzeit τ(t) > 0 festlegen; t muß τ(t) lang aktiviert sein,um zu schalten. Wir beschranken uns hier auf sichere Netze, in denen fur alle Transitionen•t 6= ∅; Schaltregel mit diskreter Zeit:

• Zustande: (M, res), wobei M eine Markierung; die Restzeit (residual time) ist eineFunktion res : T 7→ N ∪ {∞}, wobei res(t) = ∞ ⇔ ¬M [t〉. Initialer Zustand ist(MN , resN ), wobei resN (t) = τ(t) fur MN [t〉.

• 2-Phasen-Schalten, d.h. wir trennen Zeitschritte und Transitionsschalten

Zeitschritt: (M, res)[σ〉(M, res′), falls res ≥ 1 und res′ = res− 1


Transition: (M, res)[t〉(M ′, res′), falls M [t〉M ′ und res(t) = 0 ist sowie fur alle t′ mitM ′[t′〉 der Wert res′(t′) entweder τ(t′) ist, falls t′ neu aktiviert wurde (d.h. •t′∩ t• 6= ∅),oder res(t′) sonst, wenn t′ also vom Schalten von t

”unberuhrt bleibt“.

Bsp.:

s s''

s'

t

t'

t''

t'

t

1

2

1

12

Abbildung 7.8:

Ist τ(t) = 1∀ t, so erhalten wir im Prinzip die Maximumsschaltregel: M [µ〉maxM′ ⇐⇒

M [µ〉M ′ und µ ist maximal mit M [µ〉. Genauer gilt folgendes:

t2

t3

t4

t1

Abbildung 7.9:

Unter (MN , resN ) ist nur ein Zeitschritt σ moglich, nach dem alle aktivierten Transitioneneine Restzeit von 0 haben. Fur solche Zustande (M, res) gilt nun M [µ〉maxM

′ gdw. wenn furein oder alle w mit Parikh(w) = µ gilt, daß (M, res)[wσ〉(M ′, res′), wobei gemaß res′ wiederalle aktivierten Transitionen eine Restzeit von 0 haben.

Hier und im weiteren: Wann immer man eine Schaltregel definiert, ist damit auchautomatisch der entsprechende Erreichbarkeitsgraph definiert.

Hier arbeiten wir mit relativer Zeit, d.h. wir geben an wieviel Zeit seit dem letzten Zeit-punkt verstreicht, und mit 2-Phasen-Schalten; man kann auch ohne Zeitschritte arbeiten undbei jedem Schalten einer Transition eine jeweilige Zeit angeben; dabei kann (M, res)[(t, 5)〉bedeuten, daß t 5 Zeiteinheiten nach dem letzten Schalten (oder nach Systemstart beim er-sten Schalten) schaltet (relative Zeit), oder daß t 5 Zeiteinheiten nach Systemstart schaltet(absolute Zeit). Aus σσt1t2σσσt3 nach unserer Definition werden also (t1, 2)(t2, 0)(t3, 3) bzw.(t1, 2)(t2, 2)(t3, 5).

Alternativ kann man auch ein Intervall [τ1, τ2] fur die Latenzzeit angeben oder eine Schalt-dauer festlegen. Letzteres laßt sich – bis zu einem gewissen Grad – in unserem Modell be-schreiben, vgl. Abb. 7.10.

Ferner kann man auch Wahrscheinlichkeiten fur die Schaltdauer (oder fur die Auswahlzwischen verschiedenen aktivierten Transitionen) betrachten. stochastische Petrinetze.


5

a a

50

Abbildung 7.10: Transition mit Schaltdauer links, Ubersetzung rechts

7.3 Netze mit Prioritaten

Man kann N auch eine Halbordnung ⊏ auf T hinzufugen und definieren: M [t〉⊏M′, falls

M [t〉M ′ und ∀t′ : M [t′〉 =⇒ ¬ t′ ⊏ t⊏ kann z.B. durch eine Funktion prio : T 7→ N und t ⊏ t′ ⇐⇒ prio(t) < prio(t′) gegebensein.

7.4 Netze mit Inhibitor-Kanten

Stellen die Marken von s einen Vorrat dar, ware oft eine Transition t sinnvoll, zu deren Schalt-voraussetzungen M(s) = 0 gehort. Solche Transitionen widersprechen dem Grundergebnis,daß M [t〉 und M ≤ M ′ implizieren, daß M ′[t〉. Man kann aber Inhibitor-Kanten I ⊆ S × Thinzufugen und definieren: M [t〉IM

′, falls M [t〉M ′ und ∀s : (s, t) ∈ I =⇒ M(s) = 0.

ts

Abbildung 7.11:

7.5 Vergleich

Eine n-Zahlermaschine hat n Zahler c1, . . . , cn und ein Programm mit Befehlen:

• k : incr(ci) entspricht ci := ci + 1

• l: if ci = 0 then goto m else decr(ci)

2-Zahlermaschinen konnen Turingmaschinen simulieren, konnen also alles berechnen, wasuberhaupt berechenbar ist. Die Netze aus 7.4 konnen Zahlermaschinen simulieren; vgl. Abb.7.12 - die Stellen in der linken Senkrechte stellen den Programmlauf dar.


...

k

m

c

iincr c

i

cj

if c , mj

k+1

Abbildung 7.12:

Netze aus 7.3: s. Abb. 7.13

Abbildung 7.13:

Mit Maximumsschaltregel: s. Abb. 7.14

Die Netze aus 7.2, 7.3 und 7.4 sind also Turing-machtig. Es gilt: Mit Beschriftung undEndmarkierung konnen sie jede rekursiv aufzahlbare Sprache beschreiben. Sie konnen beliebi-ge Turing-Berechnungen auf den Stellen durchfuhren. Dies gilt nicht fur normale Petrinetze;Argument: Wegen der Entscheidbarkeit des Erreichbarkeitsproblems laßt sich entscheiden,ob die Sprache eines beschrifteten Netzes mit Endmarkierungen leer ist; fur Sprachen vonTuringmaschinen ist dies unentscheidbar (Satz von Rice). Genauerer Vergleich: s. Starke.


...

k

m

if c , mj

incr cic

c

i

j

k+1

Abbildung 7.14:

7.6 Kapazitaten

Oft fugt man eine Funktion k : S 7→ N ∪ {∞} hinzu (fordert MN (s) ≤ k(s) fur alle s ∈ S)und andert die Schaltregel ab:M [t〉 ⇐⇒ ∀s ∈ S : W (s, t) ≤ M(s) ∧ [W (t, s) +M(s) ≤ k(s)

bzw. M(s) +W (t, s)−W (s, t) ≤ k(s)]

Diese Varianten sind

Abbildung 7.15:

k(s) = ∞ bedeutet: keine Einschrankung Normalfallk(s) = n kann man simulieren: s. Abb. 7.16; s′ heißt Komplementplatz. Fur

”von Natur aus“

oder durch Kapazitaten beschrankte Netze kann man durch Komplementplatze Null-Abfragenin gewohnlichen Netzen modellieren.


Abbildung 7.16:

Kapitel 8

Nichtdeterminismus und modulare

Konstruktion

Konvention: In diesem Kapitel sind alle Netze beschriftet; vgl. Definition 2.11.

Kanal I

Kanal II

Kanal III

senden empfangen

s

e

s

s

e

s

e

Abbildung 8.1:

Kanal I und Kanal II haben dieselbe Sprache, nur Kanal II kann die Nachricht verlie-ren; Kanal II kann nach “senden” in eine Situation geraten, die andere Moglichkeiten bietet(namlich keine) als Kanal I. Kanal I und Kanal III hingegen sind im Prinzip gleich.

Definition 8.1 Netze N1, N2 heißen sprachaquivalent, wenn L(N1) = L(N2). ✷

Satz 8.2 Fur beschrankte Netze ist Sprachaquivalenz entscheidbar.

Beweis: Wir konstruieren aus R(N) einen endlichen Automaten AL(N), indem wir jedeKantenbeschriftung t ∈ T durch l(t) ∈ Σ ∪ {λ} ersetzen; MN ist Startzustand; alle Zustandesind Endzustande. L(AL(N)) = L(N). Sprachgleichheit bei endlichen Automaten ist ent-scheidbar. �

KAPITEL 8. NICHTDETERMINISMUS UND MODULARE KONSTRUKTION 52

Das obige Beispiel zeigt, daß Sprachaquivalenz unzureichend fur den Systemvergleich ist.

Verfeinerung der Sprachaquivalenz

Nach Aktionsfolge Vorausschau, welche Aktionen als nachstes (nicht) moglich sind:

Definition 8.3 Die ready-Semantik ready(N) ist {(w,X) | ∃M : MN [w〉〉M und X = {a ∈Σ |M [a〉〉}}. N1, N2 sind ready-aquivalent, wenn ready(N1) = ready(N2). ✷

X ist (mogliches) Menu nach w; beachte: bei M [a〉〉 konnen vor der a-Transition (interne)λ-Transitionen schalten.

N1

1s

a b

ca b

d

N2

s2

a

b

b c

d

Abbildung 8.2:

Beispiel: N1, N2 in Abb. 8.2 sind ready-aquivalent; im wesentlichen: (ab, {c}), (ab, {d}).

N3

a

a

a b

b

c

c

Abbildung 8.3:

N3 in Abb. 8.3 und N4 in Abb. 8.4 sind nicht ready-aquivalent wegenWie kann man hier N4a in Abb. 8.4 einordnen?


a

a

b

c

4N 4aNb

c

a

Abbildung 8.4:

Definition 8.4 Die Failure-Semantik (Verweigerungssemantik) F(N) ist{(w,X) |X ⊆ Σ, ∃M : MN [w〉〉M und ∀a ∈ X : ¬M [a〉〉}. X heißt Verweigerungsmenge.N1, N2 sind failure-bzw. F-aquivalent, wenn F(N1) = F(N2). ✷

Hier beschreibt X eine (mogliche) partielle Verklemmung nach w; ist X = Σ, so ist keinesichtbare Aktion mehr moglich.

Proposition 8.5 i) (w,X) ∈ F(N) ∧ Y ⊆ X =⇒ (w, Y ) ∈ F(N)

ii) (w, ∅) ∈ F(N) ⇐⇒ w ∈ L(N)

iii) (w,X) ∈ F(N) ∧ ∀a ∈ Y ⊆ Σ : (wa, ∅) /∈ F(N) =⇒ (w,X ∪ Y ) ∈ F(N)

iv) (w,X) ∈ F(N) ∧ Y ⊆ Σ \ l(T ) =⇒ (w,X ∪ Y ) ∈ F(N)

Beweis:

i), ii) klar.

iii) Sei M “passend” zu (w,X), a ∈ Y . Dann gilt ¬M [a〉〉, da sonst wa ∈ L(N) und wegenii) (wa, ∅) ∈ F(N).

iv) mit iii) und ii). �

Zusammenhang zur ready-Semantik: Ist M “passend” zu (w,X) ∈ F(N), so ist dasMenu bei M offenbar in Σ \X enthalten.

Beispiel: N3 in Abb. 8.3 und N4, N4a in Abb. 8.4 sind F-aquivalent. Wesentliche Elemente:(a,Σ \ {b}), (a,Σ \ {c}). Wegen 8.5 i) also auch (a,Σ \ {b, c}) ∈ F(N4).

N5 a

b

c

Abbildung 8.5:

N4 und N5 in Abb. 8.5 sind nicht F-aquivalent: .... N4 und N5 sind sprachaquivalent.

Schlußfolgerung aus 8.5 i): Bei der F-Semantik sind maximale Verweigerungsmengen re-levant, d.h. die (w,X) ∈ F(N), fur die (w,X ′) 6∈ F(N) fur alle X ′ ⊃ X. Man beachte,daß fur ein solches (w,X) (w,Σ \X) ∈ ready(N); die F-Semantik konzentriert sich also aufworst cases fur das Menu. Z.B. (a, {a, b, c} \ {a}) ∈ ready(N3), aber 6∈ ready(N4); fur das

”Gegenstuck“ gilt (a, {a}) ∈ F(N3) = F(N4).


Satz 8.6 Ready-Aquivalenz =⇒ F-Aquivalenz =⇒ Sprachaquivalenz,aber nicht umgekehrt.

Beweis: Ubung Wegen Umkehrung der Implikationen s. Abb. 8.4 und Abb. 8.5.

Satz 8.7 Fur beschrankte Netze ist F-Aquivalenz entscheidbar.

Beweis:Fur gegebene Netze N1 und N2, setze Ai = {l(t) 6= λ | t ist nicht tot in Ni}. Ist A1 6= A2,

so sind bereits die Sprachen der Netze verschieden, also sicher auch die F-Semantiken. Manpruft also anhand des Erreichbarkeitsgraphen, daß A1 = A2 =: A. Fur N ∈ {N1, N2} genugtes nun wegen 8.5 i), iv) zur Erfassung von F(N) Verweigerungsmengen X ⊆ A zu betrachten.Wir andern AL(N) im Beweis von 8.2 zu AF(N) ab, indem wir

• einen Zustand fail, der einziger Endzustand wird, und

• Kanten von M ∈ [MN 〉 nach fail mit Beschriftung X ⊆ A, so daß ∀a ∈ X : ¬M [a〉〉

hinzufugen (endlich, effektiv trotz λ-Kanten). Die Sprache von AF(N) ist im wesentlichenF(N) Sprachaquivalenz prufen. �

Eine Semantik Sem heißt kompositional bzgl. einer Komposition ‖, wenn sich die Se-mantik eines ‖-Gesamtsystems aus den Semantiken der Komponenten bestimmen laßt, also:Sem(N1‖N2) = Op(Sem(N1), Sem(N2)), wobei Op eine geeignete Operation ist.

Gleichbedeutend: Die von Sem induzierte Aquivalenz ist eine Kongruenz bzgl. ‖, d.h.Sem(N1) = Sem(N2) =⇒ Sem(N1‖N) = Sem(N2‖N) ∧ Sem(N‖N1) = Sem(N‖N2). Wich-tig fur den strukturierten/modularen Entwurf: Austausch aquivalenter Komponenten andertdas Gesamtverhalten nicht.


Beispiel: (fur ‖A)s. Kapitel 1 und Abb. 8.6 und 8.7. Abb. 8.7 zeigt N1‖{ds}N2: disjunkte Vereinigung +

Verschmelzen von Transitionen

dm: Daten messends: Daten sendende: Daten empfangen

N1 (Meßstation)

ds dm dm ds

init

N2 (Kanal) ds de

Abbildung 8.6:

init

dmdmds ds

de

Abbildung 8.7:

Definition 8.8 Fur A ⊆ Σ ist die parallele Komposition mit Synchronisation uber A (vgl.TCSP ) von N1 und N2 das Netz N = N1‖AN2 mit

• S = S1 × {λ} ∪ {λ} × S2 (λ als dummy)

• T = {(t1, λ) | t1 ∈ T1, l1(t1) /∈ A} ∪ {(λ, t2) | t2 ∈ T2, l2(t2) /∈ A}∪ {(t1, t2) | t1 ∈ T1, t2 ∈ T2, l1(t1) = l2(t2) ∈ A}


• W ((s1, s2), (t1, t2)) =

W1(s1, t1) falls s1 ∈ S1, t1 ∈ T1

W2(s2, t2) falls s2 ∈ S2, t2 ∈ T2

0 sonst

• W ((t1, t2), (s1, s2)) analog

• MN = MN1∪MN2

, d.h. MN (s1, s2) =

{

MN1(s1) falls s1 ∈ S1

MN2(s2) falls s2 ∈ S2

• l((t1, t2)) =

{

l1(t1) falls t1 ∈ T1

l2(t2) falls t2 ∈ T2

✷

Bemerkung: ‖A ist kommutativ und assoziativ und (∅, A, ∅, ∅, id) ist neutral (bis auf Netz-Isomorphie).

Lemma 8.9 Sei N = N1‖AN2, Mi,M′i seien Markierungen von Ni, i = 1, 2; (t1, t2) ∈

TN , (t11, t21), . . . , (t1n, t2n) ∈ TN :

i) M1∪M2[(t1, t2)〉M′1∪M

′2 ⇐⇒ M1[t1〉M

′1 ∧M2[t2〉M

′2

ii) M1∪M2[(t11, t21), . . . (t1n, t2n)〉M′1∪M

′2 ⇐⇒ M1[t11 . . . t1n〉M

′1 ∧M2[t21 . . . t2n〉M

′2.

Beweis:

i) (t1, t2) greift auf die Stellen aus S1 (genauer: S1 × {λ}) zu wie t1, auf die Stellen ausS2 wie t2 - im Fall ti = λ auf die Stellen aus Si gar nicht.

ii) nach i). �

Beachte: t1,i = λ verschwindet in t11 . . . t1n.

Lemma 8.10 Seien Mi,M′i Markierungen von Ni, i = 1, 2 und a ∈ Σ ∪ {λ}. Dann gilt in

N1‖AN2 M1∪M2[a〉〉M′1∪M

′2 genau dann, wenn

i) a ∈ A : M1[a〉〉M′1 ∧M2[a〉〉M

′2 oder

ii) a /∈ A : M1[a〉〉M′1 ∧M2[λ〉〉M

′2 oder M1[λ〉〉M

′1 ∧M2[a〉〉M

′2

Beweis: klar nach 8.9 �

Definition 8.11 Seien u, v ∈ Σ∗. Dann ist u‖Av = {w |u = u1 . . . un, v = v1 . . . vn, w =w1 . . . wn, ui, vi, wi ∈ Σ ∪ {λ}, so daß fur i = 1, . . . , n : ui = vi = wi ∈ A oder uivi = wi /∈A}. ✷

Beachte: uivi = wi =⇒ ui = λ oder vi = λ

Beispiel: bacd‖{a}cae = {bcacde, cbacde, bcaecd, bcaced . . .}

Lemma 8.12 In N1‖AN2 gilt M1∪M2[w〉〉M′1∪M

′2 genau dann, wenn es u, v gibt mit

M1[u〉〉M′1,M2[v〉〉M

′2 und w ∈ u‖Av.


Beweis:“=⇒” Induktion uber |w| mit 8.10.“⇐=” Wahle geeignete Zerlegungen u1 . . . un etc. Induktion uber n mit 8.10. �

Satz 8.13 i) L(N1‖AN2) =⋃

{u‖Av |u ∈ L(N1), v ∈ L(N2)}

ii) F(N1‖AN2) = {(w,Z) | ∃(u,X) ∈ F(N1), (v, Y ) ∈ F(N2) :

w ∈ u‖Av und Z ∩A ⊆ X ∪ Y ∧ Z \ A ⊆ X ∩ Y }

Beweis:

i) 8.12

ii) �

Korollar 8.14 Sprach- und F-Aquivalenz sind Kongruenzen bzgl. ‖A.


Anforderungen an Semantik:

i) Information uber wichtige Verhaltensmerkmale, z.B. Verklemmung

ii) kompositional

iii) nicht mehr Unterscheidungen als notig

Eine Semantik, die diese Anforderungen erfullt, unterstutzt z.B. die kompositionale Veri-fikation, welche gegen Zustandsexplosionen helfen kann. Zunachst:

|R(N1‖AN2)| ist bis zu |R(N1)| · |R(N2)|; wiederholte Komposition fuhrt zur Zustands-explosion.

Um nun interessante Eigenschaften uberN1‖AN2 festzustellen, wollen wir z.B. F(N1‖AN2)ermitteln, da F i) erfullt (vgl. 8.17), d.h. wir wollen R(N1‖AN2) bestimmen. Da dieser Graphzu groß ist, versuchen wir ein N ′

1 zu finden mit F(N ′1) = F(N1) und |R(N ′

1)| < |R(N1)| –wg. iii) haben wir da besonders viele Moglichkeiten. Wg. ii) konnen wir dann F(N ′

1‖AN2)(also R(N ′

1‖AN2)) statt F(N1‖AN2) betrachten.

Definition 8.15 Ein beschriftetes(!!) Netz heißt verklemmungsfrei, wenn (anders als bei un-beschrifteten Netzen) fur alle erreichbaren Markierungen M gilt: ∃a ∈ Σ : M [a〉〉. Zwei Netzeheißen v-aquivalent, falls beide verklemmungsfrei sind oder beide nicht. ✷

Bemerkung:

1. Falls kein a ∈ Σ unterM aktiviert ist, so kann doch eine interne Transition aktiviert sein;es kann sogar Divergenz vorliegen, d.h. eine unendliche Schaltfolge interner Transitionenaktiviert sein. (In einer Situation, wo Divergenz derart auftreten kann, daß dabei eineAktion a stets moglich bleibt, nimmt man manchmal an, daß die Divergenz dies a“verhindert”; unsere Definition fragt nur, ob a moglich ist, und ignoriert daher einesolche Divergenz.)

2. Eine Aquivalenz R′ verfeinert eine Aquivalenz R, falls R′ ⊆ R, d.h. jede Aquivalenz-klasse von R eine Vereinigung von Aquivalenzklassen von R′ ist, bzw. R′ =⇒ R.

Wir suchen nun folgende Aquivalenz:

Definition 8.16 Eine Aquivalenz heißt vollstandig abstrakt (fully abstract) bzgl. einer Men-ge von (evtl. mehrstelligen) Operationen und einer Basisaquivalenz, wenn sie die grobste (vgl.iii)) Kongruenz (vgl. ii)) bzgl. der gegebenen Operationen ist, die die Basisaquivalenz verfei-nert (vgl. i)). V A-Aquivalenz sei die vollstandig abstrakte Aquivalenz bzgl. der Operationen‖A und der v-Aquivalenz. ✷

N1

a

N2

a

λ

Abbildung 8.8:


Beispiel: Die Netze in Abb. 8.8 sind sprach- aber nicht v-aquivalent.Die Netze N4 und N5 in Abb. 8.4 und 8.5 sind sprach- und v-aquivalent; trotzdem kann

sich fur N aus Abb. 8.9 nur N‖{a, b, c}N4, nicht aber N‖{a, b, c}N5 verklemmen. V-Aquiva-lenz ist also keine Kongruenz.

N

a

d

b

Abbildung 8.9:

Proposition 8.17 N ist verklemmungsfrei ⇐⇒ ∀w ∈ Σ∗ : (w,Σ) /∈ F(N).

Beweis:Klar. �

Satz 8.18 F- und V A-Aquivalenz stimmen uberein.

Beweis:Nach 8.14: Kongruenz; nach 8.17: F-Aquivalenz =⇒ v-Aquivalenz. Da V A-Aquivalenz die

grobste Kongruenz dieser Art ist, mussen wir nur zeigen: V A-Aquivalenz =⇒ F-Aquivalenz.

Seien also N1, N2 V A-aquivalent, A := (l1(T1) ∪ l2(T2)) \ {λ}. Wir zeigen:

(*) Sei (w,X) ∈ F(N1); dann gibt es ein N , so daß fur alle N ′ mit l′(T ′) \ {λ} ⊆ A gilt:N‖AN

′ ist verklemmungsfrei ⇐⇒ (w,X) /∈ F(N ′).

Denn dann gilt: N‖AN1 und N‖AN2 sind V A-aquivalent (da V A-Aquivalenz Kongruenzist), also auch v-aquivalent. Nach (*) ist N‖AN1 nicht verklemmungsfrei, also auch nichtN‖AN2. Nach (*): (w,X) ∈ F(N2).

Demnach gilt F(N1) ⊆ F(N2) und analog F(N1) ⊇ F(N2), also F(N1) = F(N2).


Beweis von (*):Sei w = w1 . . . wn, wi ∈ Σ; X ∩A = {a1, . . . , am}; N wie in Abb. 8.10, wobei b /∈ A.

. . .

. . .

N w1

w

m

a

a

a

1

2n

b

Abbildung 8.10:

N‖AN′ ist wegen b verklemmungsfrei – es sei denn, w1 . . . wn schaltet (in N‖AN

′, alsoin N und N ′), so daß kein ai (in N‖AN

′, also in N ′) schalten kann. Also: N‖AN′ ist nicht

verklemmungsfrei ⇐⇒ (w,X ∩A) ∈ F(N ′) ⇐⇒ (w,X) ∈ F(N ′) (8.5 i) und iv)). �

Zusammenhang zum Testen

Test eines Systems N ′:

• Einbettung in Testumgebung N (❀ N‖AN′)

• Verhaltensbeobachtung; z.B. erfullt N ′ den Test, wenn N‖AN′ verklemmungsfrei ist.

(Oder wenn es in jedem Fall schließlich eine bestimmte Aktion ω von N ausfuhrt, mitder N Erfolg des Tests signalisiert. In Abb. 8.10 spielt b die Rolle von ω.)

Wir nennen dann N1 und N2 Test-aquivalent, wenn N1 und N2 dieselben Tests erfullen.

Der obige Beweis zeigt: Erfullen N1 und N2 dieselben Standardtests N gemaß (*) (wie inAbb. 8.10), so F(N1) = F(N2). Wenn aber F(N1) = F(N2), so auch immer F(N1‖AN) =F(N2‖AN) und diese Netze sind wegen 8.17 v-aquivalent.

Also stimmen F- und Test-Aquivalenz uberein. In diesem Sinn sind F-Aquivalenz undF-Semantik beobachtbar.

Documents

Petrinetze - informatik.uni-augsburg.de · Inhaltsverzeichnis 0 Literatur 2 1 Einführung 3 2 Grundbegriffe 7 3 S- und T-Invarianten 22 4 Einige Entscheidbarkeitsprobleme 27 5 Beschränktheit