Teil II.1 Wiederholung: Skript Esparza, Kapitel 1 und 2

Definition 1.3.3: Sei N ein Netz und sei M eine Markierung von N.Eine endliche Sequenz = t1 ... tn heißt von M aktivierteendliche Schaltfolge, wenn Markierungen M1, M2, ...Mn

existieren, so dass M t1 M1 t

2 M2 t3 ... t

n Mn .Eine unendliche Sequenz = t1 t2 t3 ... heißt von M

aktivierte unendliche Schaltfolge, wenn Markierungen M1, M2, ... existieren, so dass M t

1 M1 t2 M2 t3 ...

Proposition 1.3.4 Eine endliche oder unendliche Sequenz wird voneiner Markierung M aktiviert genau dann, wenn jedes endliche Präfixvon von M aktiviert wird.Lemma 1.4.1 (Das Monotonielemma) Seien M und L Markierungen eines Netzes(1) Wenn M M‘ für eine endliche Sequenz , dann (M + L) (M‘ + L) (2) Wenn M für eine unendliche Sequenz , dann (M + L)

.

Lemma 1.4.2 (Das Vertauschungslemma) Sei N (S; T; F) ein Netzund seien U, V disjunkte Teilmengen von T mit •U V• = . Sei eine (endliche oder unendliche) Sequenz von Transitionen

mit A() U V, wobei A() das Alphabet von ist (d.h. die Menge

der t aus T ist, die in vorkommen). Sei ferner =/U und =/V .

(1) Ist endlich und gilt M M‘, dann gilt M M‘ .(2) Ist unendlich, ist endlich und gilt M , dann gilt M .(3) Ist unendlich, ist unendlich und gilt M , dann gilt M .Zum Beweis vgl. Teil 1, Folie 21: Feststellung:* Seien u, v aus T mit v• •u = , dann gilt mit m[vu > m´ auch m[uv > m´.

Also können die in vorkommenden u aus U der Reihe nach „nach links gebracht“ (vor allen v aus V in ausgeführt) werden.

2.0.1 Ein Puffer mit Kapazität n

Wir modellieren einen Puffer mit Kapazität für n Nachrichten. Abbildung 2.1 zeigt das Netzsystem für n = 3. Das System besteht aus n Zellen, jeweils mit Kapazität für eine Nachricht. Die Eingabe einer neuen Nachricht wirddurch das Schalten von t1 modelliert. Das Schalten einer Transitionti, 1 <i ≤ n, bewirkt, dass die Nachricht von der Zelle i -1 in die Zelle i geht. Das Schalten von ti+1 modelliert die Ausgabe einer Nachricht.

Das System ist nichtsequentiell: z.B. gibt es erreichbare Markierungen, aus denen die Transitionen t1 und t4 völlig unabhängig voneinander schalten können.Abbildung 2.2 zeigt den Erreichbarkeitsgraphen des Puffers mit Kapazität 3.Mit Hilfe des Erreichbarkeitsgraphen kann man zeigen dass, unter anderen, die folgenden Eigenschaften gelten:

Konsistenz: Keine Zelle ist gleichzeitig leer und voll (d.h., keine erreichbare Markierung markiert gleichzeitig die Stelle si und die Stelle si+1 für i =1, 2, 3).

Sicherheit: Keine erreichbare Markierung hat mehr als eine Marke auf einer Stelle.

Deadlock-Freiheit: Jede erreichbare Markierung hat mindestens einen Nachfolger.Sogar: Jede Zelle kann immer wieder gefüllt und geleert werden (jede Transition kann immer wieder schalten).

Kapazität n: Der Puffer hat tatsächlich Kapazität n, d.h., es gibt eine erreichbare Markierung, in der alle Zellen voll sind (in der die Stellen s1, s3, s5 markiert sind).Die Anfangsmarkierung kann immer wieder erreicht werden.Zwischen zwei beliebigen erreichbaren Markierungen gibt es einen Weg mit Länge höchstens 6.

Weitere Beispiele (wechselseitiger Ausschluss (Petersons Algorithmus), Aktion/Reaktion-Protokoll).

Definition: Die Schranke einer Stelle S in einem beschränkten System (N;M0) ist die Zahl max{ M(s) | M [M0>}.(N;M0) heißt b-beschränkt, wenn keine Stelle eine größere Schranke als b hat.

In der Vorlesung werden folgende Probleme untersucht:

Verklemmungsfreiheit: Ist ein gegebenes Netzsystem (N;M0) verklemmungsfrei?

Lebendigkeit: Ist ein gegebenes Netzsystem (N;M0) lebendig?

Beschränktheit: Ist ein gegebenes Netzsystem (N;M0) beschränkt?

b-Beschränktheit: Gegeben b IN und (N;M0), ist (N;M0) b-beschränkt?

Erreichbarkeit: Gegeben ein Netzsystem (N;M0) und eine Markierung M von N, ist M erreichbar aus M0 , d.h. ist M [M0>?

Proposition 2.2.2(1) Ist (N;M0) lebendig, so ist (N;M0) verklemmungsfrei.(2) Ist (N;M0) beschränkt, so ist(N;M0) b-beschränkt für eine Zahl b.(3) Ist (N;M0) beschränkt, so hat (N;M0) nur endlich viele erreichbare Markierungen.

Beweis. (1) und (2) folgen ummittelbar aus den Definitionen. (3) folgt aus den Definitionen und aus der Tatsache, daß ein Netzsystem nur endlich viele Stellen und Transitionen hat.

Definition 2.2.3 (Wohlgeformte Netze) Ein Netz N ist wohlgeformt, wenn eine lebendige und beschränkte Markierung von N existiert.

Wir werden auch folgendes Problem betrachten:Wohlgeformtheit: Ist ein gegebenes Netz N wohlgeformt?

II.2 Skript Esparza, Teil II, Analysemethoden

Im Kapitel 3 wird gezeigt (meistens ohne Beweise), dass die Probleme Verklemmungsfreiheit, Lebendigkeit, Beschränktheit, b-Beschränktheitund Erreichbarkeit entscheidbar sind. Die Algorithmen, die diese Probleme lösen, haben aber eine sehr hohe Komplexität, und Ergebnisse der Komplexitätstheorie zeigen, dass keine effizienten Algorithmen für diese Probleme existieren.Weil Effizienz unentbehrlich für die praktische Anwendung ist, muss man sich mit Halbentscheidungsalgorithmen für allgemeine Systeme oder mit Entscheidungsalgorithmen für eingeschränkte Systemklassen zufrieden geben.Unter einem effizienten Halbentscheidungsalgorithmus für die EigenschaftP verstehen wir einen schnellen positiven (negativen) Test für P: Wenn die Eingabe den Test besteht, dann gilt P (nicht P), wenn nicht, dann kann man nichts über P sagen.

Kapitel 4 ist den Halbentscheidungsalgorithmen gewidmet.

In Kapitel 5 werden effiziente Entscheidungsalgoritmen für drei Systemklassen entwickelt: S-, T-, und Free-Choice-Systeme.

II.2.1 Ein Algorithmus für das Beschränktheitsproblem

Das Problem b-Beschränktheit ist offensichtlich entscheidbar: Wenn das Eingabe-Netz (N;M0) n Stellen hat, dann gibt es (b+1)n b-beschränkte Markierungen des Netzes N. Um b-Beschränktheit zu entscheiden, kann man denErreichbarkeitsgraphen von (N;M0) schrittweise konstruieren, bis entweder die Konstruktion terminiert oder bis eine erreichbare Markierung gefunden wird, die nicht b-beschränkt ist.Beschränktheit ist offensichtlich rekursiv aufzählbar: Man konstruiert wieder den Erreichbarkeitsgraphen des Systems, Schritt für Schritt. Wenn das System beschränkt ist, dann terminiert die Konstruktion, weil es nur endlich viele erreichbare Markierungen gibt. Für unbeschränkte Systeme terminiert die Konstruktion nicht, und man erhält keine Antwort.

Wir zeigen nun, dass Beschränktheit nicht nur rekursiv aufzählbar, sondern sogar entscheidbar ist. Dafür brauchen wir das folgende wichtige Lemma:

Lemma 3.1.1: Jede unendliche Folge A0, A1, A2, ... Aj, ... INk mit

|{ Ai | i IN }| = enthält eine unendliche monotone Teilfolge

Aj0 < Aj1 < Aj2 < ... < Ajm < ... mit jn < jn+1 für n IN. [Dabei sei (a1,a2, ..., ak) < (b1,b2, ..., bk) gdw. ai ≤ bi für alle i mit 1≤i≤k und ap < bp für mindestens ein p mit 1≤p≤k.]Beweis: Durch Induktion über k.Basis: k = 1. Trivial, weil dann alle Ai IN. Man kann die Teilfolge so aufbauen: Es sei Ajm+1 die kleinste der Zahlen An mit n >jm und An > Ajm .

Schritt: k > 1. Jedes Ai = (ai1, ... ai

k) wird zerlegt inAi‘ = (ai

1, ... aik-1) und ai

k. Wir setzen Ai = (Ai‘ | aik).

Mindestens eine der Mengen A‘ = { Ai‘ | i IN } oder

A = { a | Es existieren i IN und Ai‘ mit (Ai‘|a) = Ai } muss unendlich sein, wenn |{ Ai | i IN }| = gilt.

Ist AA endlich, also A‘ unendlich, dann gibt es eine nat. Zahl c, die als k-te Komponente in unendlich vielen Elementen Ai der gegebenen Folge auftritt; d.h. für diese Elemente giltAn = (An‘|c), wobei n { p1, p2, p3, ... } IN und stets pm < pm+1.

Für die Folge der zugehörigen An‘ folgt aus der Induktionsannahme, dass eine unendliche monotone TeilfolgeAh1‘ < Ah2‘ < Ah3‘ < .... existiert. Dann ist(Ah1‘|c) < (Ah2‘|c) < (Ah3‘|c) < .... eine unendliche monotone Teilfolge der ursprünglich gegebenen Folge.

Ist A‘ endlich, so gibt es analog zum vorigen Fall ein (k-1)-Tupel C = (c1, c2, ... , ck-1), das in unendlich vielen Ai auftritt; diese haben also die Form An = (C|an), wobei n { p1, p2, p3, ... } IN und stets pm < pm+1.

Zur Folge der apj gibt es eine unendliche monotone Teilfolgeah1 < ah2 < ah3 <... . Also ist (C, ah1) < (C, ah2) < (C|ah3) < ... eine unendliche monotone Teilfolge der gegebenen Folge.

Seien nun AA und A‘ unendlich.

Aufgrund der Induktionsannahme für die Folge der Ai‘ gibt es eine unendliche monotone Teilfolge Ah1‘ < Ah2‘ < Ah3‘ < .... der Folge der Ai‘.

Aus der Teilfolge (Ah1‘, ah1), (Ah2‘, ah2), (Ah3‘, ah3), ...

der Folge der Ai lässt sich eine unendliche monotone Teilfolge der ursprünglichen Folge gewinnen, indem eine unendliche monotone Teilfolge der Folgeah1, ah2, ah3, .... konstruiert wird - etwa die Folge aq1 < aq2 < aq3 < ....

Mit den zugehörigen Aqi‘ erhält man daraus die gesuchte Teilfolge

(Aq1‘, aq1), (Aq2‘, aq2), (Aq3‘, aq3), ... . Fertig.

Satz 3.1.2 (N;M0) ist unbeschränkt gdw. es Markierungen M und L gibt mit L ≠ 0 und M0 * M * (M + L).

Bew.: : Aus dem Monotonielemma folgtM0 * M * (M + L) * (M + 2•L) * ... .Also ist [M0> unendlich und (N,M0) unbeschränkt.

: Wenn (N,M0) unbeschränkt ist, dann ist [M0> unendlich.

Zwischenbehauptung: Da [M0> unendlich ist, gibt es eine unendliche Schaltfolge M0 t1 M1 t2 M2 t3 ... mit|{Mi |i IN}| = .

Bew.: Da T endlich ist, hat jedes M aus [M0> nur endlich viele direkte Nachfolger M‘ mit M t M‘ und t T.Der Markierungsgraph des Netzsystems (N,M0) hat also endlichen Ausgangsgrad. Wenn auf jedem unendlich langen Weg im Graphen von M0 aus nur endlich viele verschiedene M aus [M0> vorkämen, müßte [M0> endlich sein. (Vgl. Lemma von König)

Aus Lemma 3.1.1 folgt, dass in der Schaltfolge Markierungen Mi und Mj auftreten mit Mi < Mj und M0 * Mi * Mj .

Mit M = Mi und L = Mj - Mi folgt dann die Behauptung.

Satz 3.1.3 Es gibt einen Algorithmus, der entscheidet, ob ein gegebenes Netzsystem (N;M0) beschränkt ist.

Beweis: Der Algorithmus konstruiert breadth first immer größere endliche Teile des Erreichbarkeitsgraphen, und testet nach Hinzufügen jeder neuen Kante, ob es eine Schaltsequenz M0 * M * (M + L)mit L ≠ 0 gibt.Der Algorithmus terminiert entweder, wenn eine solche Sequenz gefunden wird, oder wenn keine neue Kante hinzugefügt werden kann. Im ersten Fall antwortet der Algorithmus „unbeschränkt" und im zweiten Fall „beschränkt".

Wenn (N;M0) beschränkt ist, dann ist der erste Terminierungsfall unmöglich - wegen Satz 3.1.2. Weil es nur endlich viele erreichbare Markierungen gibt, kommt aber der zweite Fall irgendwann einmal vor. Also terminiert in diesem Fall der Algorithmus und gibt die korrekte Antwort aus.

Wenn (N;M0) unbeschränkt ist, dann gibt es unendlich viele erreichbare Markierungen, und der zweite Terminierungsfall ist unmöglich. Wegen Satz 3.1.2 kommt aber der erste Terminierungsfall irgendwann einmal vor. Also terminiertder Algorithmus auch in diesem Fall und gibt die korrekte Antwort aus.

Bemerkung: Platzkomplexität O( 2n ), n Anzahl der Stellen und Transitionen.

II.2.2 Algorithmen für die restlichen Probleme

Die Entscheidbarkeit des Erreichbarkeitsproblems war ca. 10 Jahre lang offen und wurde von Pro. E.W. Mayr 1980 in seiner Dissertation (an der TUM) bewiesen. Leider ist der Algorithmus zu kompliziert für diese Vorlesung (hyperexponentieller Platz!).Wir werden nur zeigen, dass Verklemmungsfreiheit sich auf Erreichbarkeit reduzieren lässt. D.h. wir zeigen: Wenn es einen Algorithmus für Erreichbarkeit gibt, dann gibt es auch einen Algorithmus für Verklemmungsfreiheit. Zusammen mit dem Ergebnis von Pro. Mayr wird so gezeigt, dass Verklemmungsfreiheit entscheidbar ist.

Der Beweis erfolgt in zwei Schritten.Wir betrachten zuerst das folgende Hilfsproblem P.P: Gegeben ist ein Netzsystem (N;M0) und eine Menge R Svon Stellen von N. Gibt es eine erreichbare Markierung M mitM(s) = 0 für alle s R?

Dann zeigen wir, dass Verklemmungsfreiheit auf P, und P auf Erreichbarkeit reduzierbar ist.

Satz 3.2.1: Verklemmungsfreiheit ist auf P reduzierbar.

Beweis. Sei (N;M0) ein Netzsystem, und sei N = (S; T; F). Definiere S = { R S | t T : •t R ≠ }d.h., ein Element von S enthält für jede Transition t mindestens eine Stelle im Vorbereich von t. Die folgenden zwei Aussagen sind unmittelbare Konsequenzen der Definition von S:(1) S ist endlich.(2) Eine Markierung M von N ist tot, gdw. die Menge RM = { s S | M(s) = 0 } der Stellen, die von M nicht markiert werden, Element von S ist.(Denn M tot heißt t T: s •t: M(s) = 0, was RM S bedeutet.)

(N,M0) ist verklemmungsfrei, wenn für kein M [M0> gilt RM

S. Mit einem Algorithmus zur Entscheidung von P kann man für jede der endlich vielen Mengen R aus S entscheiden, ob ein M aus [M0> existiert mit R = RM.

Also kann man mit einem Algorithmus für P entscheiden ob (N,M0) verklemmungsfrei ist.

Satz 3.2.2: P ist auf Erreichbarkeit reduzierbar.

Beweis: Seien (N;M0) ein Netzsystem mit N = (S; T; F) und R eineMenge von Stellen von N. Wir konstruieren ein neues System (N‘,M0‘), indem wir neue Stellen, Transitionen, Kanten und Marken zu (N,M0) hinzufügen. Das machen wir in zwei Etappen (Abb. 3.1):

• Füge neue Stellen s0 und r0 hinzu. Lege eine Marke auf s0.• Füge eine Transition t0 sowie Kanten (s0, t0) und (t0, r0) hinzu.• Für jede Transition t T füge die Kanten (s0, t) und (t, s0) hinzu.

Nur solange s0 markiert bleibt, können die Transitionen von T ungehindert schalten. Die Transition t0 kann jedoch jederzeit schalten, und wenn sie dies tut werden alle Transitionen von T „tot", d.h. das System (N;M0) wird „gefroren".

• Für jede Stelle s S\R füge eine neue Transition ts und die Kanten (s, ts), (r0, ts), (ts, r0) hinzu.Wenn eine Marke auf r0 liegt, dann können die Transitionen ts schalten. Diese Transitionen „entleeren" die Stellen in S\R.Damit ist die Definition von (N‘,M0‘) beendet.

Sei Mr die Markierung von N‘, bei der nur auf r0 eine Marke liegt, und sonst keine. Dann gilt:

(1) Wenn es eine erreichbare Markierung M von (N,M0) gibt, die keine Stelle von R markiert, dann ist Mr erreichbar in (N‘,M0‘).Um Mr zu erreichen, schalte man erst Transitionen von T solange, bis M erreicht wird. Dann schalte man die Transition t0, und anschließend Transitionen ts, bis keine Marken mehr auf den Stellen von S liegen.

(2) Wenn Mr erreichbar in (N‘, M0‘) ist, dann gibt es eine erreichbare Markierung M von (N,M0), die keine Stelle von R markiert.Mr kann nur erreicht werden, wenn die Transition t0 schaltet und vor dem Schalten dieser Transition keine Marken auf Stellen von R liegen (denn die Stellen von R können später nicht entleert werden). M ist die Markierung von N vor dem Schalten von t0.

Aus (1) und (2) folgt: Um zu entscheiden, ob es eine erreichbare Markierung M von (N,M0) gibt, die keine Stelle von R markiert, reicht es, das System(N‘,M0) zu konstruieren, und dann zu entscheiden, ob die Markierung Mr erreichbar ist. Mit einem Algorithmus für Erreichbarkeit kann man also P entscheiden.

II.2.3 Algorithmen für beschränkte Netzsysteme

In vielen Fällen der Praxis ist leicht zu zeigen, daß ein Netzsystem beschränkt ist. Dann ist die Menge der erreichbaren Markierungen endlich, und der Erreichbarkeitsgraph kann im Prinzip berechnet und gespeichert werden. Wenn der Erreichbarkeitsgraph vorhanden ist, dann sind Beschränktheit, b-Beschränktheit und Erreichbarkeit trivial. Wir zeigen nun, dass Verklemmungsfreiheit und Lebendigkeit sich auch leicht lösen lassen.

Sei G = (V;E) der Erreichbarkeitsgraph eines Systems (N,M0). Wir definieren die Relation * VV auf die folgende Weise:M * M‘ gdw. M * M‘ und M‘ * M.

* ist offensichtlich eine Äquivalenzrelation auf V . Jede Äquivalenzklasse ≠ V‘ V von * definiert mitE‘= E (V‘V) eine starke Zusammenhangskomponente (V‘,E‘) von G.Starke Zusammenhangskomp. sind durch die Relation < geordnet:(V‘,E‘) < (V“,E“), wenn V‘≠V“ und M‘V‘, M“V“: M“[M‘>.Bem.: Es genügt zu fordern,dass M‘V‘, M“V“: M“[M‘> gilt.

Definition 3.4.1: Eine starke Zusammenhangskomponente heißt maximal, wenn sie maximal bezüglich der Ordnung < ist.

Proposition 3.4.2: Sei (N,M0) ein Netzsystem.1. (N,M0) ist verklemmungsfrei gdw. jeder Knoten seines

Erreichbarkeitsgraphen einen Nachfolger hat.2. Falls das System (N,M0) beschränkt ist, ist es lebendig gdw. in jeder maximalen starken Zusammenhangskomponente des Erreichbarkeitsgraphen für jede Transition t von N eine Markierung existiert, die t aktiviert.Beweis: Trivial.

Mit Hilfe dieser Charakterisierung lassen sich Algorithmen für Verklemmungsfreiheit und Lebendigkeit in beschränkten Petrinetzen ableiten, die linear in der Größe des Erreichbarkeitsgraphen sind. Leider kann die Anzahl der erreichbaren Markierungen exponentiell in der Größe des Netzes wachsen.Deswegen sind die Algorithmen, die den Erreichbarkeitsgraphen konstruieren, zwar sehr nützlich, aber keine endgültige Lösung der Verifikationsprobleme.

II.3 Skript Esparza: Halbentscheidungsmethoden

II.3 Lineare Algebra und lineare Programmierung

In den nächsten zwei Sektionen werden wir Systeme von linearen Gleichungen und Ungleichungen mit ganzzahligen Koeffizienten konstruieren, die partielle Informationen über unsere Verifikationsprobleme liefern.

Sei A eine Matrix und seien X und b Vektoren.

Wir werden Aussagen folgender Art beweisen:

„Wenn das Ungleichungssystem A•X ≤ b eine rationalzahlige Lösung hat, dann ist das Netzsystem (N,M0) beschränkt“

(hinreichende Bedingung) oder

„Wenn die Markierung M erreichbar ist, dann hat das Gleichungssystem A•X = b eine natürlichzahlige Lösung" (notwendige Bedingung).

Diese Aussagen führen unmittelbar zu Halbentscheidungsalgorithmen für Beschränktheit und die restlichen Verifikationsprobleme.

Die Komplexität dieser Algorithmen hängt von der Komplexität ab, Lösungen für die verschiedenen Gleichungssysteme zu finden.

Die Größe eines Gleichungssystems A•X = b oder einesUngleichungssystems A•X ≤ b mit A =(aij) , i=1,...n, j=1,....m und b = (bj) , j=1,...m definieren wir als

Summe aller log2|aij| und log2|bj| für 1 ≤ i ≤ n, 1 ≤ j ≤ m.

Das Problem, zu entscheiden, ob A•X = b eine

- rationale Lösung hat, ist in polynomieller Zeit lösbar,- ganzzahlige Lösung hat, ist in polynomieller Zeit lösbar- natürlichzahlige Lösung hat, ist NP-vollständig.

Die Markierungsgleichung

Def. (Die Inzidenzmatrix) Die Inzidenzmatrix N : (ST) ist definiert durch

Eine Markierung m von N wird als |S|-stelliger Spaltenvektor M über /N geschrieben.

N(s,t) = { 0 falls (s, t) F und (t, s) F oder (s, t) F und (t, s) F-1 falls (s, t) F und (t, s) F 1 falls (s, t) F und (t, s) F

s2

t1

t2

t4

s1

s4

s3

s5

t3

t3t1 t2 t4

s1

s2

s3

s4

s5

1 0 1 0 1 0 0 1

1 -1 0 0

0 1 - 1 0

0 1 0 -1

Def. (Die Markierungsgleichung) Die Markierungsgleichung eines Netzsystems (N, M0) mit N = (S, T, F) ist

M = M0 + N · X (X Unbekannte)

mit Variablen M (|S|-stelliger Vektor) und X (|T|-stelliger Vektor).

Lemma (Das Markierungsgleichungslemma)Sei N ein Netz und sei M [ >M’ eine Schaltfolge von N. Dann gilt M’ = M + N ·

Def. (Parikh-Vektor einer Transitionsfolge)Sei eine endliche Folge von Transitionen. Der Parikh-Vektor †N von wird definiert als Spaltenvektordurch (t) = Anzahl der Vorkommen von t in

Die Markierungsgleichung führt zu Halbentscheidungsalgorithmen für Beschränktheit, b-Beschränktheit, (Nicht)-Erreichbarkeit, und Verklemmungsfreiheit:

Satz: Sei (N, M0) ein System. Wenn das Optimierungsproblem

maximize s S

M(s)

subject to M = M0 +N · X

eine optimale Lösung n hat , dann ist (N, M0) n- beschränkt.

Satz: Sei (N, M0) ein System und sei L eine Markierung von N.Wenn die Gleichung

L = M0 + N · X (nur X als Variable)

keine Lösung hat, dann ist L nicht von M0 erreichbar.

Satz: Sei (N, M0) ein 1-beschränktes System mit N = (S, T, F).Wenn das folgende System von Gleichungen und Ungleichungenkeine Lösung hat, dann ist (N, M0) verklemmungsfrei.

M = M0 + N · X

s •t

M (s) <| t| für jede Transition t.•

S- und T-Invarianten

Satz: (Fundamentale Eigenschaft von S-Invarianten)Sei (N, M0 ) ein markiertes Netz und I eine S-Invariante von N.Wenn M von M0 aus erreichbar ist dann gilt I · M = I · M0 .

Satz: I ist eine S-Invariante von N gdw. t T:

s •t

I(s) = s t •

I(s).

Def. Ein Vektor I: S heißt S-Invariante, wenn I · N = 0.IQ

Definition 4.3.5 (Semi-positive und positive S-Invarianten) Sei I eine S-Invariante von N = (S; T; F). I ist semi-positiv, wenn 0 ≤ I und I ≠ 0;I ist positiv, wenn I > 0 (d.h. I(s) > 0 für jedes s aus S). < I >= {s S | I(s) > 0} bezeichnet die Trägermenge einer semi-positiven Invarianten I.

Proposition 4.3.6 [Eine hinreichende Bedingung für Beschränktheit]Sei (N;M0) ein System. Wenn N eine positive S-Invariante I besitzt, dann ist (N;M0) beschränkt.

Genauer: (N;M0) ist n-beschränkt mit

n = max { I•M0/I(s) | s aus S ).

Proposition 4.3.7 (Eine notwendige Bedingung für Lebendigkeit) Wenn (N;M0) lebendig ist, dann gilt I•M0 > 0 für jede semi-positive S-Invariante von N.

Beweis. Sei I eine semi-positive S-Invariante und sei s eine Stelle von <I>.

Da (N;M0) lebendig ist, existiert eine erreichbare Markierung M, die s markiert, d.h. M(s) > 0. Da I semi-positiv ist, gilt I•M I(s)•M(s) > 0. Da I eine S-Invariante ist, gilt I•M0 = I•M >0 .

Diese zwei Propositionen führen ummittelbar zu zwei effizienten Halbentscheidungsalgorithmen für Beschränkheit bzw. für Lebendigkeit.

Definition 4.3.8 (Die Relation ~ ) Seien M und L Markierungen und I eine S-Invariante des Netzes N. M und L stimmen überein bezüglich I,wenn I•M = I•L.

Wir schreiben M ~ L, wenn M und L bezüglich allerS-Invarianten von N übereinstimmen.

Proposition 4.3.9 [Eine notwendige Bedingung für Erreichbarkeit] Sei (N;M0) ein Netzsystem. Für M [M0> gilt M ~ M0.

Der folgende Satz erlaubt, effizient zu entscheiden, ob M ~ L für zwei gegebene Markierungen M und L gilt.

Satz 4.3.10: Sei N ein Netz und seien M und L zwei Markierungen von N. M ~ L gdw. die Gleichung M = L + N X eine rationale Lösung hat.

Beweis. () : M und L stimmen auf den Elementen einer Basis {I1, ... , Ik} des Vektorraums aller S-Invarianten überein. Für jeden Vektor Ij dieser Basis gilt Ij•(L-M) = 0 Nach linearer Algebra gilt: Die Spalten von N enthalten eine Basis des Lösungsraums von Ij•X = 0; (1≤j≤k).

Damit ist (L-M) Linearkombination über Q dieser Spalten, d.h. die Gleichung N•X = (L-M) hat eine rationale Lösung

() : Sei I eine S-Invariante von N. Mit I•N = 0 gilt

I•L = I•M+I•N•X = I•M. ---------

Wir haben also die folgenden Implikationen:M ist erreichbar aus L M = L + N•X hat eine Lösung X IN|T|

M = L +N •X hat eine Lösung X Q|T|

M ~ L

Satz: J ist eine T-Invariante gdw. s S: t •s

J(t) = t s •

J(t).

Def. Ein Vektor J : T heißt T-Invariante, wenn N · J = 0.IQ

Satz: (Fundamentale Eigenschaften von T-Invarianten)Sei eine Sequenz von Transitionen von N, die von einer Markierung M aktiviert wird. Der Parikh-Vektor ist eine T-Invariante von N gdw M [ M.

Beweis. () : Sei M‘ die Markierung mit M[ M‘. Aus der Markierungsgleichung folgt M‘ = M + N• .

Mit N• =0 gilt M=M‘

() : Aus der Markierungsglg. folgt M = N + N• und

daher N• = 0.

Satz 4.4.4: Ist ein markiertes Netz lebendig und beschränkt (d.h. wohlgeformt), so besitzt es eine positive T-Invariante (positiv ~ alle Komponenten positiv).

Bew.: Habe N die lebendige und beschränkte Markierung M0.

Wg. Lebendigkeit ex. eine unendliche Folge 1, 2, 3, ... endlicher Sequenzen von Transitionen i , in denen jeweils alle Transitionen von N vorkommen, so daß gilt: Mi[i+1>Mi+1 für alle i= 0, 1, 2, 3, ....

Wg. Beschränktheit können nicht alle Mi verschieden sein,

d.h. es ex. i<j mit Mi = Mj. Dann gilt Mi[i+1... j > Mi ,

und J = „Summe der Parikh-Vektoren der k“ ist eine T-Invariante.

J ist positiv, weil in der Folge i+1... j jede Transition mindestens einmal vorkommt.

Siphons und Traps

Def. R S heißt Siphon, wenn •R R • Satz: (Fundamentale Eigenschaft von Siphons) Sei R Siphon von (N, M) und gelte M[ > M’.

Aus M(R) = 0 folgt dann M’(R) = 0 (M(R) ~ Anzahl der Marken von M in R).

Betrachten von nun an Netze ohne isolierte Stellen und mit T ≠ ø

•R R• impliziert: Die Transitionen, die R markieren können, können nur schalten, wenn R schon markiert ist.Also: Nichtmarkierte Siphons bleiben nicht markiert.

Satz: (Notwendige Bedingung für Lebendigkeit)Ist (N, M0) lebendig, so gilt M(R) ≠ 0für jeden Siphon R ≠ ø von N.

Satz: Ist (N, M0) verklemmt, so ist die Menge der Stellen, die von M0 nicht markiert sind, ein nichtleerer Siphon.

Folgerung: Werden in (N, M0) von jeder erreichbaren Markierung alle Siphons markiert, so ist (N, M0) verklemmungsfrei.

Beweis. Sei R ein echter Siphon von N und sei s aus R. Wg. Lebendigkeit ex. erreichbare Markierung M, die s markiert. Damit markiert M auch den Siphon R. Aus der Proposition 4.5.3 folgt, daß auch M0 den SiphonR markiert.

Beweis. Sei R = {s | M0(s) = 0}. Zu jeder Transition t ex. Stelle s aus •t mit M0(s) = 0 (sonst wäre t aktiviert). Also enthält R alle Transitionen von N. Es folgt •R R•.

Die Existenz eines unter M0 nicht markierten Siphons kann in polynomieller Zeit mit Hilfe des folgenden Algorithmus getestet werden. Der Algorithmusberechnet den größten Siphon, der in einer gegebenen Menge R von Stellen enthalten ist. Es reicht also, R zu wählen als die Menge der Stellen s mit M0(s) = 0.

Input: Ein Netz N = (S; T;F) und R S.Output: Q R.Initialisierung: Q = R.beginwhile es gibt s in Q und t in •s mit t ≠Q• doQ:= Q\ {s}endwhileend

Def. R S heißt Trap, wenn R • • R

Satz: (Fundamentale Eigenschaft von Traps) Sei R ein Trap und M[ > M’. Aus M(R) > 0 folgt dann M’(R) > 0.

Satz: (Hinreichende Bedingung für Verklemmungsfreiheit) Enthält jeder nichtleere Siphon von N einen von M0 markierten Trap so ist (N, M0) verklemmungsfrei.

II.4 Systemklassen mit effizienten Verifikationsalgorithmen.

In den drei Sektionen des Kapitels untersuchen wir drei Systemklassen: S-Systeme, T-Systeme und Free-Choice-Systeme.

Alle Sektionen haben eine ähnliche Struktur. Nach der Definition der Klasse, werden drei Sätze vorgestellt: der Lebendigkeitssatz, der Beschränkheitssatz, und der Erreichbarkeitssatz.

Der Lebendigkeitssatz charakterisiert die Systeme der Klasse, dielebendig sind. Der Beschränkheitssatz charakterisiert die lebendigen Syste-men, die beschränkt bzw. b-beschränkt sind. Der Erreichbarkeitssatz charakterisiert die erreichbaren Markierungen der lebendigen und beschränkten Systeme.

Der Beweis dieser drei Sätze benötigt oft einige Ergebnisse überdie Struktur der S- und T-Invarianten der Systeme, die ebenfalls vorgestellt werden.

5.1 S-Systeme

Definition 5.1.1 (S-Netze, S-Systeme) Ein Netz heißt S-Netz, wenn |•t| =1 = |•t| für jede Transition t. (N;M0) heißt S-System, wenn N ein S-Netz ist.

Proposition 5.1.2 (Fundamentale Eigenschaft von S-Systemen)Sei (N;M0) ein S-System, S die Menge der Stellen in N0 und M eine erreichbare Markierung. Dann gilt M0(S) = M(S).

Satz 5.1.3 (Lebendigkeitssatz) Ein S-System (N;M0) ist lebendig, gdw. N stark zusammenhängend ist und M0 mindestens eine Stelle markiert.

Satz 5.1.4 (Beschränktheitssatz) Ein lebendiges System (N;M0) istb-beschränkt, gdw. M0(S) ≤ b.

Satz 5.1.5 (Erreichbarkeitssatz): Seien (N;M0) ein lebendiges S-System und M eine Markierung von M. M ist erreichbar, gdw. M0(S) = M(S).

Proposition 5.1.6 (S-Invarianten von S-Netzen) Sei N = (S, T,F) ein zusammenhängendes S-Netz. Ein Vektor I : S Q ist eine S-Invariante vonN, gdw. I = (x, ... ,x) für eine Zahl x aus Q.

5.2 T-Systeme

Definition 5.2.1 (T-Netze, T-Systeme) Ein Netz heißt T-Netz, wenn |•s| = 1 = |s•| für jede Stelle s. Ein System (N;M0) heißt T-System, wenn N einT-Netz ist (Es heißt markierter Graph, wenn es ausserdem stark zusammenhängend ist).

Proposition 5.2.2 (Fundamentale Eigenschaft von T-Systemen) Seien ein Kreis eines T-Systems (N;M0) und M eine erreichbare Markierung. Dann gilt M() = M0().

5.2.1 LebendigkeitSatz 5.2.3 (Lebendigkeitssatz) Ein T-System (N;M0) ist lebendig, gdw. M0() > 0 für jeden Kreis von N.

5.2.2 BeschränkheitSatz 5.2.4 (Beschränktheitssatz) Ein lebendiges T-System (N;M0) istb-beschränkt gdw. jede Stelle s in einem Kreis mit M0() ≤ b enthalten ist.

Korollar 5.2.5 Sei (N;M0) ein lebendiges T-System

1. Eine Stelle ist beschränkt gdw. sie zu einem Kreis gehört.

2. Sei s eine beschränkte Stelle, dann gilt max{ M(s) | M0 * M } = min{ M0() | enthält s }

3. (N;M0) ist beschränkt gdw. N stark zusammenhängend ist.

5.2.3 Erreichbarkeit

Für den Erreichbarkeitssatz müssen wir erst die T-Invarianten von T-Netzen näher betrachten:

Proposition 5.2.6 (T-Invarianten von T-Netzen) Sei N = (S, T, F) ein zusammenhängendes T-Netz. Ein Vektor J: T Q ist eine T-Invariantegdw. J = (x, ... , x) für eine Zahl x aus Q.

Satz 5.2.7 (Erreichbarkeitssatz) Sei (N;M0) ein lebendiges T-System.Eine Markierung M ist erreichbar gdw. M0 ~ M.

5.2.4. Weitere Eigenschaften

Satz 5.2.8 Sei (N;M0) ein stark zusammenhängendes T-Netz. Die folgenden Aussagen sind äquivalent:(1) (N;M0) ist lebendig.(2) (N;M0) ist verklemmungsfrei.(3) (N;M0) hat eine unendliche Schaltsequenz.

Satz 5.2.9 (Genrich'scher Satz) Sei N ein stark zusammenhängendes T-Netz mit mindestens einer Stelle und einer Transition. Es gibt eine Markierung M0 von N, so daß (N;M0) lebendig und 1-beschränkt ist.

5.3 Free-Choice-Systeme

Def. 5.3.1 (Free-Choice-Netze, Free-Choice-Systeme) Ein Netz N = (S; T; F) heißt free-choice, wenn •t s• F für jedes s aus S und t aus T mit (s; t) F. Ein System (N;M0) heißt free-choice, wenn N ein Free-Choice-Netz ist.

Proposition 5.3.2 (Alternative Definitionen von Free-Choice-Netzen)

(1)Ein Netz ist free-choice, wenn für alle Transitionen t1, t2 gilt: (t1 ≠ t2 ^ •t1•t2 ≠ ) •t1 = •t2 .

(2) Ein Netz ist free-choice, wenn für alle Stellen s1, s2 gilt: (s1 ≠s2 ^ s1• s2•≠ ) s1• = s2•

5.3.1 Lebendigkeit

Satz 5.3.3 (Commoner'scher Lebendigkeitssatz) Ein Free-Choice-System (N;M0) ist lebendig gdw. jeder Siphon von N einen unter M0 markiertenTrap enthält.

Satz 5.3.4 (Komplexität) Das Problem

Gegeben: Ein free-choice System (N;M0)Frage: Ist (N;M0) nicht lebendig?

ist NP-vollständig.

5.3.2 Beschränkheit

Definition 5.3.5 (S-Komponente) Sei N = (S, T, F) ein Netz und sei N‘ = (S‘, T‘, F‘)

ein Teilnetz von N. N‘ heißt S-Komponente von N, wenn es die folgenden Bedingungen erfüllt:

1. T‘ = •S‘ S‘• 2. N‘ ist stark zusammenhängend.

Proposition 5.3.6 Sei (N;M0) ein System und sei N‘ = (S‘, T‘, F‘) eineS-Komponente von N. Für jede erreichbare Markierung M gilt M0(S‘) = M(S‘).

Satz 5.3.7 (Hack'scher Beschränktheitssatz) Sei (N;M0) ein lebendiges free-choice System. (N;M0) ist beschränkt gdw. jede Stelle von N ineiner S-Komponente enthalten ist.

Proposition 5.3.8 (Schranken von Stellen) Sei (N;M0) ein lebendiges und beschränktes free-choice System, und sei s eine Stelle von N. Es giltmax{M(s) | M0 * M} =min{M0(S‘) | S‘ ist die Menge der Stellen einer S-Komponente von N}.

Definition 5.3.9 (Cluster) Sei N = (S, T, F) ein Netz.Ein Cluster ist eine Äquivalenzklasse der Relation((F (S T)) (F (S T))-1)*

Satz 5.3.10 (Rangssatz) Ein Free-Choice-System (N;M0) ist lebendig und beschränkt gdw. die folgenden Bedingungen gelten:1. N hat eine positive S-Invariante.2. N hat eine positive T-Invariante.3. Rang (N) = c -1, wobei c die Anzahl der Cluster von N ist.4. Jeder Siphon von N ist unter M0 markiert.

5.4 Erreichbarkeit

Wenn P ≠ NP, dann kann es leider keinen polynomiellen Algorithmus für Erreichbarkeit in Free-Choice-Netzen geben, weil:Satz 5.4.1 Erreichbarkeit für lebendige und beschränkte free-choice Systeme ist NP-vollständig.

Satz 5.4.2 (Erreichbarkeitssatz) Sei (N;M0) ein lebendiges, beschränktes und zyklisches Free-Choice-System. Eine Markierung M von N ist erreichbar aus M0 gdw. M0 ~ M.

Korollar 5.4.3 Das Problem

Gegeben: ein lebendiges, beschränktes und zyklisches Free-Choice-System (N;M0) und eine Markierung MFrage: Ist M erreichbar?

ist in polynomieller Zeit lösbar.

Dieses Ergebnis ist nur nützlich, wenn man effizient entscheiden kann, ob ein lebendiges und beschränktes Free-Choice-System zyklisch ist. Der folgendeSatz sagt, daß das der Fall ist:

Satz 5.4.4 Ein lebendiges und beschränktes Free-Choice-System (N;M0) ist zyklisch gdw.jeder Trap von N unter M0 markiert ist.