-
Zur Startseite
Zum Editor

Zum Tutorial

PetriEdiSim

Tutorial zum Thema "Petri-Netze"
2.   Petri-Netze
2.4   Erreichbarkeit



Vorheriges Kapitel    Nächstes Kapitel

2.4   Erreichbarkeit

Zustände von Automaten besitzen einen statischen und einen dynamischen Aspekt. Statische Zustände sind Teil der Stuktur des Automaten. Dynamisch gesehen entscheidet jeder Zustände der gerade aktiv ist das zukünftige Verhalten des Automaten. In Netzen teilen sich diese statischen und dynamischen Zustände in Plätze und Markierungen auf. Deshalb unterscheiden wir zwei Formen von Erreichbarkeit bei einem Netz N = ( A, Pl, ->, M0).

Eine (dynamisch) erreichbare Markierung von N ist eine Markierung M für die es Zwischenmarkierungen M1, ... , Mn und globale Transitionen 1, ... , n gibt mit

M0 M1 · · · Mn = M.


Notation : mark(N) = Menge der erreichbaren Markierungen von N
[M0 = mark(N)
[M = die von M aus erreichbaren Markierungen.

In der Definition von mark(N) genügt es, lokale Transitionen ti statt i zu betrachten.

Die Menge place(N) der statisch erreichbaren Plätze von N ist die kleinste Teilmenge von Pl mit :


(1) M0 place(N)

(2) Wenn I place(N) und I O eine Transition von N ist, so gilt O place(N).



Beispiel :
N = place(N) = { p1, p3 }



Hierzu noch folgende Bemerkung :

{ p Pl | M mark(N) : p M } place(N)


  Anfang der Seite


Schwache Isomorphie

Im folgenden wird hauptsächlich mit sicheren Netzen gearbeitet, dies bedeutet, daß keine Plätze mit mehreren Token vorkommen.
Weiterhin ist es gelegentlich wünschenswert die Existenz von Plätzen zu ignorieren und Plätze, die nicht statisch erreichbar sind, zu vergessen. Dies geschieht durch die Einführung von geeigneten Notationen des Isomorphismus und abstrakten Netzen.


Definition :
Zwei Netze Ni = ( Ai , Pli , ->i , M0i ) mit i= 1,2 sind schwach isomorph, abgekürzt
N1 = isom N2
falls A1 = A2 und es eine Bijektion
ß : place( N1 ) -> place( N2 )
gibt mit
ß( M01 ) = M02
und für alle I, O place( N1 ) und alle u A1 { }
I 1 O gdw. ß( I ) 2 ß( O )

ß heißt schwacher Isomorphismus zwischen N1 und N2.

Als Veranschaulichung des Konzepts ein Beispiel :

Beispiel :
N1 = = isom = N2



= isom ist eine Äquivalenz-Relation auf Netzen.
Bei diesem Beispiel wird durch die Bijektion ß    p 1 auf q 1 abgebildet
und p 3 auf q 2.



Definition :
Ein abstraktes Netz ist eine Isomorphieklasse eines konkreten Netzes N
[N]= isom    = { N' | N = isom N' }
abgekürzt
[N]
ANetz ist die Klasse aller abstrakten Netze.

Für abstrakte Netze wird die gleiche graphische Darstellung wie für Netze verwendet. Es muß lediglich sicher gestellt werden, daß alle Plätze statisch erreichbar sind und ihre Bezeichnungen gelöscht werden.


Wichtige Eigenschaft

Ein (konkretes) Netz N heißt sicher, falls
M mark(N)    p Pl :    M(p) 1.
Ein abstraktes Netz [N] heißt sicher, falls
N sicher ist.


  Anfang der Seite


Die Beziehung zwischen Netzen und Automaten ist durch den Interleaving- Fallgraph gegeben. Dieser kann auch als Erreichbarkeitsgraph bezeichnet werden.


Definition :
Der Interleaving-Fallgraph eines Netzes N = ( A , Pl , -> , M0 ) ist der Automat
A(N) = (A , mark(N) , ->A , M0 )
wobei für alle M , N mark(N) und alle u A { } gilt
M A N ,
falls es in N eine Transition t gibt mit act(t) = u und M N in N.

Für abstrakte Automaten :    A( [N] ) = [ A(N) ]


Beispiel :
[N] =


A( [N] ) =



Vorheriges Kapitel    Nächstes Kapitel


© Copyright Oktober 1997 by Petra Hornstein