PetriNetze

PetriNetze, auch Petri-Netze genannt, sind formale Modelle zur Beschreibung und Analyse von verteilten, parallelen und synchronen Abläufen. Sie bestehen aus Stellen (Places), Transitionen (Übergängen) und Kanten (Bögen). Tokens repräsentieren Ressourcen oder Zustände. Die Gesamtheit der Tokens in allen Stellen heißt Markierung. Der Graph ist bipartiert: Stellen und Transitionen wechseln sich als Knotentypen ab, Kanten verbinden nur Stellen mit Transitionen.

Der Ablauf ergibt sich aus der Semantik der Netze: Eine Transition ist aktiviert (enabled), wenn in jedem Eingangsplatz die benötigte Tokensanzahl vorhanden ist. Beim Feuern werden Tokens aus den Eingangsplätzen konsumiert und Tokens in den Ausgangsplätzen erzeugt. Durch wiederholtes Feuern entsteht eine Dynamik des Systems, wobei mehrere Transitionen konkurrieren oder parallel feuern können. Die abstrakte Semantik erlaubt verschiedene Ausführungsordnungen und modelliert damit neben deterministischen auch konkurrierende Abläufe.

Wichtige Eigenschaften von PetriNetzen sind Erreichbarkeit, Liveness (Lebensfähigkeit), Sicherheit (Begrenztheit der Tokenanzahl) und Boundednesse bzw. Kantenzustandbarkeit. Analysen nutzen oft die Inzidenzmatrix, Erreichbarkeitsmengen, Invarianten (Stabilitäts- und Zuweisungsinvarianten) sowie Baum- und graphentheoretische Techniken, um mögliche Verläufe, Deadlocks oder Fehlerzustände zu identifizieren.

Es gibt verschiedene Varianten: klassische Stellen-Übergangsnetze (P/T-Netze), farbige PetriNetze (Coloured Petri Nets) zur kompakteren Modellierung komplexer Daten, zeitbasierte Netze, stochastische Netze und Hochstufen-Netze (High-Level Petri nets). Anwendungen finden sich in Fertigung und Logistik, Geschäftsprozessen, Workflow-Management, Protokollen und verteilten Systemen. Zur Analyse und Simulation werden Tools wie CPN Tools, PIPE, WoPeD oder Renew eingesetzt.

PetriNetze wurden von Carl Adam Petri 1962 eingeführt und haben sich seit den 1980er-Jahren als Standardwerkzeug in Informatik, Systemtechnik und Prozessmodellierung etabliert.