Ein Petri-Netz ist ein mathematisches Modell von nebenläufigen Systemen. Die ursprüngliche Form der Petri-Netze nennt man auch Bedingungs- oder Ereignisnetz. Endliche Automaten und Bedingungs- oder Ereignisnetze sind gleichmächtig. Petri-Netze wurden durch Carl Adam Petri in den 1960er Jahren definiert. Sie verallgemeinern wegen der Fähigkeit, nebenläufige Ereignisse darzustellen, die Automatentheorie.

Funktionsweise

---

Petrinetz.png Ein Petri-Netz ist ein bipartiter und gerichteter Graph. Er besteht aus Stellen bzw. Plätzen (Places) und Übergängen bzw. Transitionen (Transitions). Stellen und Transitionen sind durch gerichtete Kanten verbunden. Es gibt keine direkten Verbindungen zwischen zwei Stellen oder zwei Transitionen.

einfaches_petrinetz.pngStellen werden als Kreise, Transitionen als Rechtecke dargestellt. Jede Stelle hat eine Kapazität und kann entsprechend viele Token, Marken bzw. Zeichen enthalten. Ist keine Kapazität angegeben, steht das für unbegrenzte Kapazität oder für eins. Jeder Kante ist ein Gewicht zugeordnet, das die Kosten dieser Kante festlegt. Ist einer Kante kein Gewicht zugeordnet, wird der Wert eins verwendet.

Sind alle Kapazitäten der Stellen und Kanten eines Petri-Netzes 1, so wird es auch als Bedingungs-/Ereignis-Netz bezeichnet.

Die Belegung der Stellen heißt Markierung und ist der Zustand des Petri-Netzes.

Transitionen sind aktiviert bzw. schaltbereit, falls sich in allen Eingangsstellen mindestens so viele Marken befinden, wie die Transitionen Kosten verursacht und alle Ausgangsstellen noch genug Kapazität haben, um die neuen Marken aufnehmen zu können. Schaltbereite Transitionen können zu einem beliebigen Zeitpunkt schalten. Beim Schalten einer Transition werden aus deren Eingangsstellen entsprechend der Kantengewichte Marken entnommen und bei den Ausgangsstellen entsprechend der Kantengewichte Marken hinzugefügt. Merke: Marken werden in einem Petri-Netz nicht bewegt. Sie werden entfernt und erzeugt!

Die Marken eines Petri-Netzes sind in ihrer einfachsten Form voneinander nicht unterscheidbar. Für komplexere, aussagekräftigere Petri-Netze sind Markeneinfärbungen, Aktivierungszeiten und Hierarchien definiert worden.

Wichtige Begriffe

---

Lebendigkeit:

Eine Transition heißt

• tot, falls sie unter keiner Folgemarkierung aktiviert ist.
• aktivierbar, falls sie unter mindestens einer Folgemarkierung aktiviert ist.
• lebendig, falls sie in jeder erreichbaren Markierung aktivierbar ist.

Ein Petri-Netz heißt

• tot, falls alle Transitionen tot sind.
• todesgefährdet, falls das Petri-Netz unter einer Folgemarkierung tot ist.
• verklemmungsfrei oder schwach lebendig, falls es unter keiner Folgemarkierung tot ist.
• (stark) lebendig, falls alle Transitionen lebendig sind.

Erreichbarkeit: Eine Markierung eines Petri-Netzes heißt erreichbar, falls es eine Schaltsequenz der Transitionen gibt, welche die Startmarkierung in diese Markierung überführt.

Konservativität: Ein Petri-Netz heißt konservativ, falls die (beliebig) gewichtete Summe der Marken konstant ist.

Beschränktheit: Ein Petri-Netz heißt beschränkt, wenn es für jede Stelle eine Schranke b gibt, so daß nie mehr als b Marken in einer Stelle liegen. Ein Petri-Netz heißt 1-beschränkt, wenn b = 1, 2-beschränkt, wenn b = 2 ...

Sicherheit: Ein Petri-Netz heißt sicher, falls es 1-beschränkt ist.

Formale Definition

---

Ein Petri-Netz ist ein 6-Tupel (P,T,F,K,W,m₀). Durch das 3-Tupel (P,T,F) ist ein bipartiter und gerichteter Graph definiert.

• P, nichtleere Menge von Plätzen P = {p₁,p₂,...,p_|P|}
• T, nichtleere Menge von Transitionen (Übergängen) T = {t₁,t₂,...,t_|T|}
• F, nichtleere Menge der Kanten (Flussrelation) F ⊆ (P × T) ∪ (T × P)
• K, Kapazitäten der Plätze, Kapazitätsfunktion K : P → $\backslash mathbb\{N\}\backslash ,\backslash cup\backslash ,\backslash \{\backslash infty\backslash \}$
• W, Kosten der Kanten, Gewichtsfunktion W : F → $\backslash mathbb\{N\}$
• m₀, Startmarkierung m₀ : P → $\backslash mathbb\{N\}$

Die Mengen der Plätze P und Transitionen T sind disjunkt (formal: $P\; \backslash cap\; T\; =\; \backslash emptyset$). Die aktuelle Markierung $m\; :\; P\; \backslash rightarrow\; \backslash mathbb\{N\}$ bezeichnet man als Zustand des Petri-Netzes. m(p) ist die Anzahl der Marken auf Platz p.

Folgende (Teil-)Mengen sind für $t\; \backslash in\; T$ definiert:

• Vorbereich $\backslash bullet\; t\; =\; \backslash lbrace\; p\; \backslash in\; P\; |\; (p,t)\; \backslash in\; F\; \backslash rbrace$, also alle Plätze, von denen eine Kante zur Transition t führt,
• Nachbereich $t\backslash bullet\; =\; \backslash lbrace\; p\; \backslash in\; P\; |\; (t,p)\; \backslash in\; F\; \backslash rbrace$, also alle Plätze, zu denen eine Kante von der Transition t aus führt.

Schaltbereitschaft

Eine Transition t heißt aktiviert, schaltbereit oder hat Konzession, falls gilt:

1. ∀p ∈ •t : m(p) ≥ W(p,t)
2. ∀p ∈ t•\•t : K(p) ≥ m(p) + W(t,p)
3. ∀p ∈ t•∩•t : K(p) ≥ m(p) - W(p,t) + W(t,p)

Schaltvorgang

Eine aktivierte Transition t kann schalten. Falls sie schaltet werden für alle Plätze p die Anzahl der Marken wie folgt neu berechnet:

m'(p) = m(p) - W(p,t)	falls p ∈ •t und p ∉ t•
m'(p) = m(p) + W(t,p)	falls p ∉ •t und p ∈ t•
m'(p) = m(p) - W(p,t) + W(t,p)	falls p ∈ •t und p ∈ t•
m'(p) = m(p)	sonst

Anwendungsgebiete

---

• Asynchroner Schaltkreis
• Datenanalyse
• Nebenläufige Programmierung
• Paralleler Algorithmus
• Softwareentwurf
• Verwaltung von Arbeitsabläufen
• Verifikation von nebenläufigen Prozessen.
• Automatisierung (Steuerungstechnik)
• Stoffstromnetz

Werkzeuge

---

• JARP - lokale Java-Anwendung - Editor zum Erstellen und Simulieren von einfachen Petrinetzen. Intuitive Bedienung, veränderbare Größe und Lage von Objekten und Beschreibungen, unbegrenzte Textlänge, einfache Layout-Hilfen. Durch grüne/rote Transitionen eindeutige Visualisierung der feuerbereiten Übergänge. In v1.1 noch einige Bugs beim Öffnen, Speichern und Drucken.

• PNS - An S/T Petri-Net Simulation System ist ein sehr leicht bedienbares Java Applet zum schnellen Ausprobieren. Auch als Download-Version verfügbar, kann dann Netze auch speichern (am besten mit java jpns als Application aufrufen). Beschreibungen zu Objekten können lang sein, aber ihre Position ist nicht veränderbar.

Werkzeuge (für Fortgeschrittene)

---

• SIPN-Editor (ein Editor für signalinterpretierte Petrinetze (SIPN)) - Java - Funktioniert nicht ohne Anpassungen von Pfaden.
• LoLA (a Low Level Petri net Analyzer) - LoLA ist ein expliziter Model-Checker für Petrinetz-Modelle
• INA (Integrated Net Analyzer) - Dos - Keine Graphische Oberfläche
• ARP (ARP im WWW) - Analysator -
• Maria (Maria im WWW) - Dos - Analysator
• PEP (PEP im WWW) - unter Win nicht ohne cygwin verwendbar
• PIPE2 (PIPE im WWW) - Platform Independent Petri Net Editor 2
• Renew (Tool für objektbasierte Petrinetze) - Simulation funktioniert nicht "out of the box"
• Tina (Tina im WWW) - nichts für jemanden der mal ein wenig mit Petrinetzen rumspielen will
• Design/CPN (Tool für die farbigen Petri Netze) - Kostenpflichtig
• Visual Object Net++ (Tool für hybride Petri Netze) - Testversion auf 200 Elemente limitiert.
• Snoopy (Snoopy im WWW) - Software tool; dient dem Erstellen und animieren hierarchischer Petri-Netze
• Cool Modes (Collide Forschungsgruppe) - Download nach Registrierung möglich; inklusive Simulation, graphischer Oberfläche und mit weiteren visuellen Modellierungssprachen - Java
• Peneca Chromos (Technische Universität Ilmenau) - Programm zur Simulation von Petri-Netzen, nur gegen persönliche Unterschrift erhältlich
• WoPeD open-source Java-Editor für Workflow Nets und Place/Transition Nets
• Netlab (Institut für Regelungstechnik) - Windowsprogramm, graphischem Editor, Analysefunktionen für verschiedene Graphen und Invarianten, Integration in Matlab
• PED (Petri-Netz Editor 1.0) - Ein Windowsrogramm zum Erstellen und Simulieren von Petri-Netzen

Siehe auch

---

Nebenläufigkeit - Verifikation - Verklemmung - Lebendigkeit

Literatur

---

• Aalst, Wil van der ; Hee, Kees van: Workflow Management - Models, Methods, and Systems, The MIT Press, 2002, ISBN 0-262-01189-1
• Abel, Dirk: Petri-Netze für Ingenieure - Modellbildung und Analyse diskret gesteuerter Systeme, Berlin: Springer Verlag, 1990, ISBN 3-540-51814-2
• Baumgarten, Bernd : Petri-Netze - Grundlagen und Anwendungen, Heidelberg: Spektrum Akademischer Verlag, 1996, ISBN 3-8274-0175-5
• König, Rainer ; Quäck, Lothar: Petri-Netze in der Steuerungs- und Digitaltechnik, München: Oldenbourg, 1988, ISBN 3-486-20735-0
• Priese, Lutz ; Wimmel, Harro: Theoretische Informatik - Petri Netze, Berlin: Springer Verlag, 2003, ISBN 3-540-44289-8
• Reisig, Wolfgang: Petrinetze - Eine Einführung, Berlin: Springer, 1990, ISBN 3-540-16622-X
• Starke, Peter H.: Analyse von Petri-Netz-Modellen, Stuttgart: B.G. Teubner, 1990, ISBN 3-519-02244-3
• Zuse, Konrad: Petri-Netze aus der Sicht des Ingenieurs, Braunschweig: Vieweg, 1980, ISBN 3-528-09615-2

Weblinks

---

• Einführungskurs mit interaktiven Beispielen
• Fachgruppe "Petrinetze und verwandte Systemmodelle" der Gesellschaft für Informatik
• Petri Nets World (englisch)

Theoretische Informatik | Parallelverarbeitung

شبكات بيتري | Petri net | Red de Petri | Réseau de Petri | Petri-háló | Petrinet | Sieć Petriego | Rede de Petri | Reţea Petri | Мережа Петрі | Petri网