Abbildungsverzeichnis   II

Inhaltsverzeichnis

Abbildungsverzeichnis   III

  Übersicht der Definitionen.  IV

1  Einleitung  1

2  Petri-Netze: Einordnung und Überblick  2

2.1  Definitionen und Varianten  2

2.2  Einordnung von Petri-Netzen in die Graphentheorie  4

2.3  Anwendungsgebiete von Petri-Netzen  6

2.4  Elemente, Begriffe und Zusammenhänge in S/T-Systemen.  8

2.4.1  Graphische Strukturelemente und deren Bedeutung.  8

2.4.2  Grundbegriffe der Schaltdynamik  10

2.4.3  Nebenläufigkeit und Nichtdeterminismus  12

3  Wichtige Struktur- und Dynamik-Aspekte von S/T-Systemen  15

3.1  Struktureigenschaften von Netzen.  15

3.1.1  Schlichtheit  15

3.1.2  Konflikte.  15

3.1.3  Netzklassen.  17

3.2  Statische Transformationen und ihre Bedeutung.  20

3.3  Zustandsänderungen und ihre Darstellungsmöglichkeiten.  23

4  Fazit  26

Anhang A:  Exemplarische Erreichbarkeitsanalyse und Erreichbarkeitsgraph  28

Anhang B:  Beispiel für algebraische Bestimmung von Zustandsänderungen.  29

Literaturverzeichnis   31

Abbildungsverzeichnis   

Abbildungsverzeichnis   

Abb.  1: Prof. Dr. C. A. Petri  

Abb.  2: Elemente eines Petri-Netzes und ein Beispiel-Netzgraph  

Abb.  3: S/T-System zum Netz aus Abb. 2  

Abb.  4: Beispiele für logisches UND und ODER  

Abb.  5: Knoten- und Kantenmengen zu einem Netz  

Abb.  6: Schaltvorgang anhand des IV-MFallstudien-Seminars WS04/05  

Abb.  7: Sperrkante  

Abb.  8: Beispiel für lokalen Nichtdeterminismus und Nebenläufigkeit  

Abb.  9: Markenweiche zur Vermeidung eines Nichtdeterminismus  

Abb.  10: Beispiele für Konflikte im Vor- und Nachbereich  

Abb.  11: Beispiele für Synchronisations-Elemente  

Abb.  12: Beispiele für Netzklassen  

Abb.  13: Konfliktlösende Einbettung  

Abb.  14: Faltung eines unendlichen Netzes zu einem endlichen  

Abb.  15: Eine Schlinge  

Abb.  16: Ein S/T-System samt Inzidenzmatrix und Zustandsvektor  

Abb.  A1: Ein S/T-System D  

Abb.  A2: Erreichbarkeitstabelle zu D  

Abb  A3: Erreichbarkeitsgraph zu D  

Übersicht der Definitionen IV

Übersicht der Definitionen

Definition 1: Petri-Netze (informell) 2

Definition 2: Petri-Netze (formell) 3

D e f i n i t i o n 3 : S / T - S y s t e m 3

Definition 4: Bipartiter, gerichteter Graph 5

Definition 5: Kantengewichtung und Stellenkapazität 9

Definition 6: Aktiviertheit 10 Definition 7: Schaltung 11

Definition 8: Nebenläufigkeit 12

Definition 9: Nichtdeterminismus 13 Definition 10: Schlichtheit 15

D e f i n i t i o n 1 1 : K o n f l i k t 1 5

Definition 12: Zustandsmaschine 18

Definition 13: Synchronisationsgraph 19

Definition 14: Isomorphismus 20 Definition 15: Einbettung 20 Definition 16: Verfeinerung 22

D e f i n i t i o n 1 7 : F a l t u n g 2 2

Definition 18: Erreichbarkeitsmenge 24

Kapitel 1: Einleitung 1

1 Einleitung

Petri-Netze sind, wie einst von Peter Stahlknecht als ironischer Hinweis auf ihren Verbreitungs- und Bekanntheitsgrad bemerkt, keine Instrumente zum Fische fangen. Vielmehr handelt es sich bei Petri-Netzen um eine der seltenen deutschen Beiträge zur theoretischen Informatik, die weltweit und auch in der USamerikanischen Fachöffentlichkeit wahrgenommen wurden [vgl. ROS91, S. 1].

für Anwender noch immer weithin unbekannt ist [vgl. SCH02, S. 8], haben Petri-Netze in der akademischen Welt bereits eine weite Verbreitung und Beachtung erfahren. 2004 fand bereits zum 25. Mal die „International Conference on Application and Theory of Petri Nets“ ¹ statt, eine Fachgruppe der deutschen „Gesellschaft für Informatik“ beschäftigt sich mit Petri-Netzen ² und neben vielen anderen hat auch Konrad Zuse ein Buch über Petri-Netze geschrieben ³ .

Da es sich bei dieser Ausarbeitung um die erste in einer Sequenz von sechsen zum Thema Petri-Netze handelt, wird im zweiten Kapitel besonderer Wert darauf gelegt, einen Überblick über die allgemeinen Eigenschaften und Arten von Petri-Netzen und deren Grundbegriffe zu geben. Das dritte Kapitel beschäftigt sich tiefer gehender zum einen mit ausgewählten statischen Struktureigenschaften und Transformationen von Petri-Netzen. Zum Anderen wird dort auch eine Einführung in die dynamischen, also im Zeitablauf auftretenden Zustands-

¹ http://www.cs.unibo.it/atpn2004/(Stand: 05.01.2005)

² http://www.informatik.uni-hamburg.de/TGI/GI-Fachgruppe0.0.1/index.html (Stand: 05.01.2005)

³ Zuse, K.: „Petri-Netze aus der Sicht des Ingenieurs“, Vieweg-Verlag, 1982

Kapitel 2: Petri-Netze: Einordnung und Überblick 2

veränderungen und deren Darstellungsmöglichkeiten gegeben. Sofern von Bedeutung, finden sich auch Hinweise auf die Bedeutung für den Entwurf und die Anwendung von Petri-Netzen. Um einen größeren Zusammenhang herzustellen, wird an entsprechenden Stellen dieser Arbeit kurz auf die weiteren Ausarbeitungen zum Thema Petri-Netze verwiesen.

2 Petri-Netze: Einordnung und Überblick

2.1 Definitionen und Varianten

Petri-Netze stellen ein geeignetes Mittel dar, um den zeitlichen Ablauf eines Systems und dessen Zustandsänderungen graphisch zu repräsentieren und erfüllen daher die gleiche Funktion wie Zustandsgraphen [vgl. SCH02, S. 11].

Definition 1: Petri-Netze (informell): Petri-Netze lassen sich informell zweckmäßig definieren als ein Modellierungswerkzeug, mit dessen Hilfe man reale oder logische Systeme beschreiben kann, bei denen bestimmte Objekte durch Ereignisse verbraucht und erzeugt werden [vgl. BB96, S. 15-17].

Von Petri-Netzen existieren drei verschiedene Varianten [vgl. BE03, S. 116-119]: x Bedingungs/Ereignis-Netze (B/E-Netze) zeichnen sich dadurch aus, dass jedes modellierte Ereignis nur unter 1 bis n Bedingungen eintritt, die jeweils entweder erfüllt sind oder nicht [vgl. BB96, S. 111-115].

x Stellen/Transitions-Netze (S/T-Netze) besitzen die gleichen Elemente wie B/E-Netze. Bedingungen für Ereignisse haben nun nicht nur den Status „erfüllt“ oder „nicht erfüllt“, sondern werden durch eine quantifizierbare Menge von nicht unterscheidbaren Objekten, genannt „Marken“, charakterisiert. Graphisch werden Marken oft als kleine, schwarze Punkte dargestellt. „Erfüllt“ ist eine Bedingung erst dann, wenn ein bestimmter Grenzwert von Marken erreicht ist.

Kapitel 2: Petri-Netze: Einordnung und Überblick 3

x Prädikat/Transitions-Netze (Pr/T-Netze) unterscheiden sich von S/T-Netzen insofern, als dass die Marken, die gemeinsam eine Bedingung für ein Ereignis darstellen, nun auch individuell verschieden, also unterscheidbar sein können ⁴ .

Es ist möglich, die einzelnen Varianten in einander zu überführen. So kann beispielsweise ein S/T-Netz in ein B/E-Netz überführt werden [vgl. BB96, S. 114-115]. Diese Arbeit beschäftigt sich ausschließlich mit S/T-Netzen bzw. S/T-Systemen. S/T-Systeme bestehen zum einen aus einem Petri-Netz.

Definition 2: Petri-Netz (formell):

Ein Petri-Netz oder Netzgraph ist formell durch das Tripel (S, T, F) definiert [vgl. BB96, S. 50; BE03, S. 115].

S steht hierbei für die Menge aller objektaufnehmenden Behälter, genannt „Stellen“ oder „Plätze“, T für die Menge aller Ereignisse, genannt „Transitionen“ und F für die Menge aller existierenden Verbindungen zwischen Stellen und Transitionen, genannt „Kanten“ [vgl. BB96, S. 50; SCH02, S. 15-16] (Abb. 2, siehe auch Abb. 5).

Definition 3: S/T-System:

Ein S/T-System wird formell durch das 6-Tupel (S, T, F, K, W, M0) beschrieben [vgl. BB96, S. 79-80].

Gemeinsam mit einer Menge von Kapazitäten der objektaufnehmenden Stellen K, einer Menge von Kantengewichten W und einer Anfangs-Ausstattung mit

⁴ siehe Ausarbeitung „Petri-Netze mit individuellen Marken“