-
Zur Startseite
Zum Editor

Zum Tutorial

PetriEdiSim

Tutorial zum Thema "Petri-Netze"
2.   Petri-Netze
2.6   Struktureigenschaften



Vorheriges Kapitel    Nächstes Kapitel

2.6   Struktureigenschaften

In diesem Kapitel soll folgende Frage untersucht werden :

Können die die Eigenschaften des Tokenspiels eines Netzes
aus seiner statischen Struktur abgelesen werden ?

Es wird erlätert, daß dies für Teilklassen von Netzen möglich ist. Dazu werden folgende Netz-Eigenschaften betrachtet :

·     Sicherheit
·     Lebendigkeit

Der Begriff der Sicherheit wurde bereits im vorherigen Kapitel eingeführt, der Begriff der Lebendigkeit ist neu.

Definition :
Gegeben sei ein Netz N = ( A , Pl , -> , M0 )

(i) Eine Transition t -> heißt lebendig, falls
M mark(N)     M' [M : t   ist in M' bereit.
(iii) N heißt lebendig, falls alle Transitionen t ->
lebendig sind.


In einem lebendigen Netz können also alle Transitionen immer einmal wieder schalten. Zur Definition der hier betrachteten Netzklasse werden weitere Notationen für Netze N = ( A , Pl , -> , M0 ) benötigt :

Vorbereich eines Platzes p Pl :
· p = pre(p) = { t ->     |     p post(t) }

Nachbereich eines Platzes p Pl :
p· = post(p) = { t ->     |     p pre(t) }

Flußrelation

FN ( Pl × -> ) { -> × Pl } von N :
für alle p, q Pl und t -> gilt

p FN t , falls p pre(t)



t FN q , falls q post(t)

Die Flußrelation beschreibt also sämtliche gerichtete Kanten in der graphischen Darstellung des Netzes.

Wie üblich sei mit

FN+     die transitive Hülle von FN

und mit

FN*     die reflexive, transitive Hülle von FN

bezeichnet.


  Anfang der Seite


Nun kann die Netzklasse eingeführt werden, die hier interessiert.

Definition :
Ein markierter Graph oder Synchronisationsgraph ist ein Netz
N = ( A , Pl , -> , M0 ) mit folgenden Eigenschaften :

(i) Pl ist endlich und nicht leer.
(ii) Alle Plätze p Pl haben genau einen eingehenden Pfeil und einen ausgehenden Pfeil, d.h.

p Pl :   | pre(p) | = | post(p) | = 1.

Insbesondere sind alle Plätze p Pl unverzweigt.
(iiI) N ist stark zusammenhängend, d.h.

t1, t2 -> : t1     FN*     t2

Zwischen je zwei Transitionen gibt es also einen Weg längs der gerichteten Kanten in der graphischen Darstellung des Sychronisationsgraphen.


Beispiel :



Definition :
Sei N = ( A , Pl , -> , M0 ) ein Synchronisationsgraph.
Ein Pfad der Länge k in N ist eine Folge

= p0 t1 p1 t2 . . . tk pk     mit k 0.

von Plätzen und Transitionen von N mit folgenden Eigenschaften:

(i) i { 1, ... , k } : post( pi-1 ) = {ti} = pre( pi )
(ii) Die t1, ... , tk sind paarweise verschieden.


Der Pfad heißt Kreis oder Zyklus, falls k 1 und p0 = pk gilt.

Der Sychronisationsgraph aus dem oben gezeigten Beispiel ist aus der "Synchronisation" (dem Verschmelzen von Transitionen) zweier Kreise entstanden. Im folgenden werden einige Eigenschaften von Synchronisationsgraphen vorgestellt.

Eigenschaften von Synchronisationsgraphen

Sei N = ( A , Pl , -> , M0 ) ein Synchronisationsgraph. Dann gilt :


(i) Jeder Platz p Pl liegt auf einem Kreis von N.
(ii) Jeder Kreis von N stellt eine S-Invariante von N dar, d.h. genauer : Die charakteristische Funktion der Menge aller in vorkommenden Plätze ist eine S-Invariante.

Korollar :
Sei N = ( A , Pl , -> , M0 ) ein Synchronisationsgraph und = p0 t1 p1 t2 . . . tk pk ein Kreis von N. Dann gilt für alle M mark(N) :

  M( pi )     =       M0( pi ) ,

d.h. die Tokenanzahl auf bleibt invariant.


Satz :
(Hinreichende Bedingung für Sicherheit)
Sei N = ( A, Pl, ->, M0 ) ein Synchronisationsgraph. Wenn jeder Platz p Pl auf einem Kreis von N liegt, der mit höchstens einem Token belegt ist, dann ist N sicher.


  Anfang der Seite


Die Umkehrung des Satzes gilt jedoch nicht ! Zum Beispiel enthält das folgende Netz N einen Kreis mit zwei Plätzen, die in der Anfangsmarkierung belegt sind.

N =

Trotzdem ist N sicher, da es überhaupt nicht schalten kann. Insbesondere ist N nicht lebendig.

Für lebendige Synchronisationsgraphen kann deren Sicherheit charakterisiert werden. Dazu dienen die folgenden beiden Sätze.

Satz :
(Lebendigkeit)
Sei N = ( A, Pl, ->, M0 ) ein Synchronisationsgraph.
Dann gilt :

N ist lebendig.
<=>
Auf jedem Kreis von N gibt es mindestens einen Platz p mit p M0 .


Satz :
(Sicherheit unter Annahme von Lebendigkeit)
Sei N = ( A, Pl, ->, M0 ) ein lebendiger Synchronisationsgraph.
Dann gilt :

N ist sicher.
<=>
Jeder Platz p Pl liegt auf einem Kreis von N, der
mit genau einem Token belegt ist.


In diesem Kapitel wurde gezeigt, daß die Eigenschaften Sicherheit und Lebendigkeit schon an der statischen Struktur für Teilklassen von Netzen abgelesen werden können. Als Teilklasse wurden die Synchronisationsgraphen verwendet.

Vorheriges Kapitel    Nächstes Kapitel


© Copyright Oktober 1997 by Petra Hornstein