Direkt zum Inhalt

Lexikon der Mathematik: Petrinetz

Formalismus zur Modellierung nebenläufiger und verteilter Systeme.

Petrinetze setzen konsequent das sog. Lokalitätsprinzip verteilter Systeme um, wonach jedes im System stattfindende Ereignis nur von Bedingungen in seiner unmittelbaren Umgebung abhängt und auch nur auf solche wirkt. Die verteilte Struktur eines Systems spiegelt sich in den Stellen eines Petrinetzes wider, die in graphischen Darstellungen als Kreise dargestellt sind. Eine Stelle kann Marken (Token) beherbergen. Eine Verteilung von Marken auf die Stellen (Markierung) stellt einen Systemzustand dar. Zustandsänderungen manifestieren sich durch das Entfernen von Marken auf einigen und das Erzeugen von Marken auf anderen Stellen. Möglichkeiten zur Zustandsänderung werden durch als Rechteck gezeichnete Transitionen repräsentiert. Die Menge der Stellen, von denen eine Transition t Marken entfernt, heißt Vorbereich von t (t) und wird durch Pfeile von diesen Stellen zur Transition dargestellt. Die Menge der Stellen, auf denen t Marken erzeugt, heißt Nachbereich von t (t) und wird durch Pfeile von t zu diesen Stellen dargestellt. Die Menge der Stellen und Transitionen verbindenden Pfeile heißt Flußrelation. Eine Transition ist aktiviert bei einer Markierung, falls die durch sie zu entfernenden Marken im Vorbereich der Transition vorliegen. Ein Schalten einer Transition bewirkt eine Zustandsänderung, also das Entfernen und Erzeugen von Marken gemäß der Flußrelation. Eine Markierung m′ ist von einer Markierung m erreichbar, wenn es eine Sequenz von Schaltvorgängen gibt, die m in m′ überführt.

Die Menge aller von einer gegebenen Anfangsmarkierung erreichbaren Markierungen bildet einen nicht notwendigerweise endlichen Automaten, genannt Zustandsgraph, dessen Zustandsübergangsrelation durch das Schalten aktivierter Transitionen gegeben ist. Die zum Zustandsübergang verwendete Transition wird als Eingabezeichen aufgefaßt. Diese Beziehung zwischen Petrinetzen und Automaten gestattet das Studium das Verhaltens verteilter Systeme anhand formaler Sprachen, den Netzsprachen. Zum Studium von speziellen Phänomenen der Natur verteilter Systeme eignen sich allerdings halbgeordnete Strukturen besser als formale Sprachen.

Für Petrinetze existiert ein reiches Angebot an Analysetechniken, darunter auch strukturelle Methoden wie z. B. mittels Invarianten. S-Invarianten ordnen jeder Stelle ein Gewicht derart zu, daß die gewichtete Markensumme im Gesamtsystem sich durch das Schalten von Transitionen nicht ändert. S-Invarianten lassen u. a. Schlüsse auf (Nicht-)Erreichbarkeit von Markierungen und die Endlichkeit des Zustandsgraphen zu. T-Invarianten gewichten Transitionen derart, daß jede der Gewichtung entsprechende Schaltfolge zur Ausgangsmarkierung zurückkehrt. Damit sind sie Indizien für zyklisches Verhalten.

Beide Arten von Invarianten lassen sich als Lösungen von homogenen Gleichungssystemen über der durch die Flußrelation bestimmten Inzidenzmatrix des Netzes charakterisieren.

Es gibt viele Varianten von Petrinetzen, die sich darin unterscheiden, welche Verteilungen von Marken auf die Stellen zulässige Markierungen sind. So können z. B. Kapazitätsbeschränkungen auferlegt werden, Marken können unstrukturiert (Stellen-Transitionsnetz) oder Träger von Daten sein.

Varianten können ebenfalls das Schalten betreffen, z. B. durch die Vorgabe von Zeitrestriktionen (Zeitnetz) bzw. stochastischen Verteilungen für das Schaltverhalten.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos