Petri-Netz

Ein Petri-Netz ist eine mathematische Repräsentation von verteilten Systemen.

Petri-Netze wurden durch Carl Adam Petri in den 1960er Jahren definiert. Sie verallgemeinern wegen der Fähigkeit, nebenläufige Ereignisse darzustellen, die Automatentheorie.

Ein Petri-Netz besteht aus Systemzuständen (Stellen), Übergängen (Transitionen) und gerichteten Kanten zwischen Stellen und Transitionen, die diese miteinander verbinden. Eine Linie bzw. Bogen verbindet eine Stelle mit einem Übergang und umgekehrt. Es gibt keine direkten Verbindungen – weder zwischen zwei Stellen, noch zwischen zwei Übergängen. Stellen dürfen beliebig viele Token, Marken bzw. Zeichen enthalten. Wenn Übergänge ausgelöst werden, werden Zeichen von den Eingabepositionen verarbeitet und in Ausgabepositionen erzeugt. Ein Übergang ist aktiviert, wenn es Zeichen in jeder Eingabeposition gibt.

Die Zeichen eines Petri-Netzes sind in ihrer einfachsten Form voneinander nicht unterscheidbar. Komplexere Petri-Netze ergänzen Zeicheneinfärbung, Aktivierungszeit und Hierarchie zum Netzwerk.

Die ursprüngliche Form der Petri-Netze nennt man auch Bedingungs-/Ereignissnetz. Endlicher Automat und Bedingungs-/Ereignissnetze sind gleichmächtig.

Wichtige Begriffe

Lebendigkeit:

Ein Petri-Netz ist stark lebendig, falls jede Transition von jeder aus der Startmarkierung erreichbaren Markierung über eine bestimmte Schaltsequenz aktiviert werden kann.
Ein Petri-Netz ist schwach lebendig, falls aus jeder erreichbaren Markierung eine Transition aktiviert werden kann.
Eine Transition ist tot, wenn sie nie mehr schaltbereit wird
Eine Transition ist aktivierbar, wenn sie noch mindestens 1x schaltbereit werden kann
Eine Transition ist lebendig, wenn sie immer wieder schaltbereit werden kann

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

Konservativität: Ein Petrinetz heißt konservativ, wenn die (beliebig) gewichtete Summe der Marken stets konstant bleibt

Sicherheit: Ein Petrinetz heißt n-sicher, wenn nie mehr als n Marken auf einem Platz zu liegen kommen

Anwendungsgebiete

Asynchrone Schaltkreise
Datenanalyse
Nebenläufige Programmierung
Softwareentwurf
Verwaltung von Arbeitsabläufen
Verifikation von nebenläufigen Prozessen.

Werkzeuge

ARP (ARP im WWW)
Maria (Maria im WWW)
Tina (Tina im WWW)

Siehe auch

Literatur

Bernd Baumgarten: Petri-Netze, Spektrum Akademischer Verlag, ISBN 3-8274-0175-5
Lutz Priese, Harro Wimmel: Theoretische Informatik Petri Netze, Springer Verlag, ISBN 3-540-44289-8
Konrad Zuse: Petri-Netze aus der Sicht des Ingenieurs, Vieweg, ISBN 3-528-09615-2

Weblinks