FACHARTIKEL
Was sind und
was sollen die Petrinetze?
Aufgepasst: Dies ist eine kreative Interpretation, echte Petrinetze gibt es erst weiter unten.
Der Titel dieses Beitrags erinnert an die berühmte Schrift „Was sind und was sollen die Zahlen?“, mit der der Mathematiker Richard Dedekind im Jahr 1888 den Zahlen und Mengen eine solide wissenschaftliche Grundlage gab. In den 1960er-Jahren hat Carl Adam Petri wiederholt vorgeschlagen, derartige Grundlagen auch für die Informatik zu suchen – allerdings ohne Erfolg. Einer dieser grundlegenden Vorschläge soll hier in die Entwicklung der Informatik eingeordnet werden, historisch wie auch konzeptionell.
In den Naturwissenschaften, den Technikwissenschaften und auch in der Ökonomie wird dynamisches Verhalten traditionell als Funktion über einer kontinuierlichen Zeitachse dargestellt. Ende der 1950er-Jahre wurde deutlich, dass komplexes algorithmisches Verhalten in diskreten Schritten abläuft, also prinzipiell anders. Es erschienen erste Vorschläge zu einer Theorie schrittweise arbeitender Automaten. Berechenbare Funktionen und formale Konzepte aus der Mathematik und Linguistik wurden als Basis der Theoretischen Informatik übernommen und weiterentwickelt. Eine Berechnung wurde als endliche Sequenz einzelner Schritte aufgefasst, an deren Anfang die Eingabe und am Ende die Ausgabe vorliegt. Eine – unendliche – Menge solcher Sequenzen kann als Automat charakterisiert werden.
In dieser Situation hat Carl Adam Petri vorgeschlagen, weitere und andere Konzepte als grundlegend in einer Theorie der Informatik zu berücksichtigen: Module, die lokal unabhängig voneinander voranschreiten, Interaktion von Modulen während laufender Berechnungen, ein universelles Konzept zur Komposition von Modulen, Vermeidung globaler Sichten auf große Systeme, lokal begrenzte Ursachen und Wirkungen von Ereignissen, formale Modellierung lebensweltlicher (nicht nur symbolischer) Sachverhalte, kausale Ordnung statt zeitliche Ordnung, Invarianten in großen Systemen nach dem Vorbild der Physik (nicht bloß die vergleichsweise einfachen Schleifeninvarianten von Programmiersprachen), starke Basierung auf mathematischer Logik und einiges mehr. Die Resonanz darauf war damals gering.
Anders als von Petri vorgeschlagen, hat die Informatik einen ganz anderen Weg genommen: Ende der 1960er-Jahre stellte sich die Konstruktion von Software als ein zentrales Problem der Informatik heraus und es wurde der Begriff des Software Engineering geprägt, mit der Konzentration auf neue Programmiersprachen.
Aus damaliger und auch aus heutiger Sicht erscheint diese Entwicklung der Methoden zur Konstruktion von Software folgerichtig, zwangsläufig, ja geradezu unausweichlich. Man kann und will sich kaum vorstellen, dass es auch anders hätte kommen können. Dabei ist es doch erstaunlich, dass Programmiererinnen und Programmierer ein komplexes Ingenieur-Produkt, also Softwareprogramme, aus der Intuition heraus anfertigen, ohne allzu viele Zwischenschritte. Andere Fächer der Natur- und Ingenieurwissenschaften bilden ausgefeilte Modelle, um ihren Gegenstand besser zu verstehen.
Wie es um die Modellierung steht
Tatsächlich gab es immer wieder Vorschläge, ein System, in dem Software eine Rolle spielt, zunächst als Ganzes zu modellieren, und dann aus dem Modell für Teile des Systems Code zu erzeugen. So sagte etwa der niederländische Informatiker Edsger W. Dijkstra, Gewinner des Turing Award im Jahr 1972: „Computer Science is no more about computers than astronomy is about telescopes.“ Leslie B. Lamport, Gewinner des Turing Award 2013, ging sogar noch weiter und stellte die These auf, Software müsse wie ein Haus gebaut werden. Wie auch in der Architektur sollte ein detaillierter Plan der erste Schritt sein. Doch Lamport beobachtete das Gegenteil: Die meisten, so sagte er, würden nicht einmal eine grobe Skizze erstellen, bevor sie mit dem Coden starteten. Nun mag man einwenden, dass es ja vielerlei Modellierungssprachen gibt (darunter beispielsweise ARIS, BPMN, CASL, EPK, FOCUS, MSC, STATECHARTS, TLA, UML, Z) und dass modellgetriebene Softwareentwicklung und Metamodellierung anerkannte Forschungsthemen sind. Wirklich durchgesetzt hat sich davon nichts. Der Aufwand scheint den Ertrag nicht zu lohnen. Das liegt daran, dass viele Modellierungstechniken implementierbare Konzepte nachbilden, nicht aber Fragestellungen des zu entwickelnden Systems. Dadurch ist der konzeptionelle Unterschied zwischen (Software-) Modellen und Software gering; viele Modellierungstechniken decken nur spezielle Aspekte ab, verschiedene Konzepte breiter angelegter Techniken (beispielsweise UML) sind nicht gut integriert. Eine allgemeingültige Basis analog zu den berechenbaren Funktionen für die Programmierung gibt es für die Modellierung diskreter Systeme nicht. Petris Vorschläge dazu wurden nicht weiter beachtet.
Anforderungen an eine Modellierungsinfrastruktur
Eine lohnende Modellierungstechnik erfüllt eine Reihe von Anforderungen; insbesondere skaliert sie für große Systeme und hat eine solide wissenschaftliche Fundierung. Vor allem aber unterstützt sie die Modellierung realweltlicher, rechnerintegrierter Systeme, nicht primär die Modellierung von Software. Wer modelliert, kann Abstraktionsstufen von Komponenten frei wählen, ebenso den Grad formaler oder informeller Darstellungen. Verschiedene Modelle desselben Systems können verschiedene Aspekte betonen, mit gemeinsamen Abstraktionen und Verfeinerungen. Automatische Generierung von Code ist hingegen keine primäre Anforderung an Modelle.
Mit einem guten Modell sollte es gelingen, wichtige Systemeigenschaften zu formulieren und zu beweisen, Komplexität von Verhalten und Kosten aller Art abzuschätzen, die Funktionalität eines Systems auch Außenstehenden zu erläutern, Verträge und Gewährleistung zu vereinbaren und die Korrektheit implementierter Komponenten zu sichern. Die bislang vorgeschlagenen Modellierungstechniken erfüllen bei Weitem nicht diese Anforderungen.
Petrinetze und Aussagenlogik
Schon in den 1960er-Jahren hat Petri Lösungen für einige der obigen Anforderungen an eine gute Modellierungstechnik vorgeschlagen. Wir greifen hier seine Vorschläge zur Modellierung von Verhalten heraus.
In der wissenschaftlichen Tradition ist die Beschreibung eines Sachverhalts eine Aussage (engl. „proposition“), wie sie in der Aussagenlogik gebräuchlich ist. Klassische Logik betrachtet Aussagen, die immer gelten (z. B. 5 ist eine Primzahl); Petri schlägt nun vor, Verhaltensmodelle für Informatiksysteme mit veränderlichen Aussagen zu bilden. Ein Zustand ist dabei nichts anderes als eine Aussage, die wahr und falsch werden kann. Ein Zustand ist erreicht, wenn seine Aussage wahr ist. Mit einem Ereignis können Zustände verlassen und neue Zustände erreicht werden; es entsteht ein Schritt. Wir zeigen das am Beispiel eines Systems zweier Lieferwagen, A und B, die an einer Rampe beladen werden und die geladenen Waren unabhängig voneinander (an verschiedenen Orten) ausliefern.
Petrinetze
Ein Petrinetz ist eine mathematische Struktur aus Plätzen und Transitionen, als Graph dargestellt mit runden und eckigen Knoten. Jeder Pfeil des Graphen verbindet einen Platz mit einer Transition oder umgekehrt eine Transition mit einem Platz. Petrinetze werden verschiedenartig verwendet; in der elementarsten und bekanntesten Form, wie beispielsweise in Abb. 5, bezeichnet jeder Platz einen Zustand, der aktuell erreicht sein kann, gekennzeichnet mit einem dicken Punkt, einer Marke. In Abb. 5 sind also aktuell drei Zustände erreicht, die vier weiteren Zustände sind nicht erreicht. Eine Transition t ist aktiviert, wenn jeder an t endende Pfeil an einem erreichten Zustand beginnt. In Abb. 5 sind also zwei Transitionen aktiviert: A fährt ran und B fährt ran. Eine aktivierte Transition kann eintreten. Durch einen solchen Schritt werden einige Zustände verlassen und andere erreicht. Abb. 8 skizziert einen solchen Schritt.
Petrinetze können auch anders verwendet werden: Jedes einzelne Erreichen und Verlassen eines Zustands, und jeder einzelne Schritt, wie in den Abbildungen 1–4, kann ohne Marken dokumentiert werden.
Ein Platz kann mehr als eine Marke enthalten; die Marken können individuell gestaltet sein wie in Abb. 6 oder abstrakt beschrieben sein wie in Abb. 7. Dabei ist das Prinzip der Beschreibung einzelner Schritte immer gleich: Intuitiv formuliert, „fließen“ Marken durch die Pfeile, die an einer Transition enden oder beginnen.
Zu Petrinetzen gibt es eine umfangreiche wissenschaftliche Literatur. Es werden spezielle, anwendungsorientierte Klassen von Petrinetzen konstruiert, Analysetechniken und -werkzeuge entwickelt; seit fast 50 Jahren wird jährlich eine internationale Petrinetz-Konferenz ausgerichtet und es liegen unüberschaubar viele Anwendungsstudien vor.
Über die Autoren
Peter Fettke ist Professor für Wirtschaftsinformatik an der Universität des Saarlandes und Research Fellow am Deutschen Forschungszentrum für Künstliche Intelligenz (DFKI) in Saarbrücken. In seiner Forschung arbeitet er an der Schnittstelle zwischen der Wirtschaftsinformatik und Künstlicher Intelligenz (KI). Seine Arbeiten zählen zu den meistzitierten Artikeln international führender Zeitschriften und er gehört zu den Top 10 der meistzitierten Wissenschaftler*innen am DFKI.
Wolfgang Reisig ist emeritierter Professor für Softwaretechnik und Theorie der Programmierung der Humboldt-Universität zu Berlin. In den 1980er-Jahren war er Mitarbeiter bei Carl Adam Petri. Er ist als Verfasser mehrerer Bücher und vieler Arbeiten über Petrinetze bekannt geworden. Derzeit arbeitet er zusammen mit Peter Fettke an der Modellierungsinfrastruktur Heraklit.
Abb. 1 Drei Schritte des Lastwagens A
In der von Petri vorgeschlagenen grafischen Darstellung zeigt Abb. 1 ⓐ die beiden Zustände A ist leer und Rampe ist frei. Wenn diese beiden Zustände erreicht sind, tritt das Ereignis A fährt ran ein und der Zustand A wird beladen wird erreicht. Auf diese Weise modelliert Abb. 1 ⓐ einen Schritt des Systems. Die in den Abbildungen 1 ⓑ und 1 ⓒ modellierten Schritte sind nun offensichtlich. Ein Schritt hat also einen lokalen Charakter; er betrifft einige wenige Zustände. Die Schritte aus Abb. 1 können nun komponiert werden und so einen Ablauf bilden. Abb. 2 zeigt das Resultat; intuitiv formuliert, werden die Schritte aneinandergeschoben. So zeigt Abb. 2 eine „Runde“ des Lastwagens A. Sie beginnt und endet damit, dass der Lastwagen leer und die Rampe frei ist. Inhaltlich ist diese Runde nicht sehr spannend: Drei Ereignisse liegen hintereinander; die – lokalen – Zustände bilden klar definierte globale Zwischenzustände, in Abb. 2 durch weiße Streifen markiert. Entsprechend zeigt Abb. 3 eine Runde des Lastwagens B.
Wirklich interessant ist die Komposition dieser beiden Abläufe, dargestellt in Abb. 4: Das Ende der A-Runde und der Anfang der B-Runde haben den gemeinsamen Zustand Rampe ist frei. Damit tritt B fährt ran ein, nachdem A weggefahren ist und die Rampe frei gemacht hat. Das Ereignis A liefert aus tritt aber völlig unabhängig von den drei Ereignissen der B-Runde ein. Technisch formuliert, sind die Ereignisse nicht mehr total geordnet, sondern nur teilweise: A liefert aus ist ungeordnet zu den drei Ereignissen von B.
Dieses Konzept teilweise geordneter Ereignisse eines einzelnen Ablaufs ist unüblich in der Informatik; dabei liefert es mehr Einsichten als Sequenzen globaler Zustände und Schritte, die mit einem Zeitbegriff oder einem Beobachter motiviert werden.
Als Variante der Komposition der A-Runde und der B-Runde kann natürlich auch deren Reihenfolge vertauscht und ihr Auftreten vervielfacht werden; beispielsweise ist B-Runde • B-Runde • A-Runde ebenfalls ein sinnvoller Ablauf. Abb. 5 zeigt ein Systemmodell, das alle derartigen Verhaltensmöglichkeiten darstellt. Abb. 5 hat nun die bekannte Form eines Petrinetzes. Die anfangs erreichten Zustände sind mit einem Punkt gekennzeichnet. Der Zusammenhang zwischen Abläufen und Systemmodellen wird durch Abbildungen definiert. Ein Petrinetz ist also nicht, wie so oft dargestellt, als eine seltsame Variante des Brettspiels „Mensch ärgere dich nicht!“ (siehe Kasten) zu interpretieren. In Analogie zur Automatentheorie zeigt Abb. 5 eine Art Automat, der nicht Worte über einem Alphabet, sondern (unendlich viele) Abläufe darstellt.
Abb. 2 Drei Schritte des Lastwagens A
Abb. 3 Drei Schritte des Lastwagens B
Abb. 4 Komposition einer A_Runde und einer B_Runde
Von der Aussagen- zur Prädikatenlogik
Anstelle zweier Lastwagen und einer Rampe kann ein System beispielsweise aus fünf Lastwagen und drei Rampen bestehen. Eine entsprechende Darstellung mit den Ausdrucksmitteln aus Abb. 5 wäre äußerst aufwendig und nicht intuitiv. Da bietet es sich an, systematisch von der Aussagenlogik zur Prädikatenlogik zu wechseln.
Abb. 5 Systemmodell für alle beliebig komponierten Abläufe
Für Lastwagen x werden die drei Aussagen x ist leer, x wird beladen und x ist voll ersetzt durch die Prädikate leere Lastwagen, ladende Lastwagen und volle Lastwagen. Die Aussage Rampe ist frei wird durch das Prädikat freie Rampen ersetzt. Abb. 6 zeigt dieses Modell. Jedes Prädikat p wird als Kreis dargestellt und mit den Objekten beschriftet, auf die p aktuell zutrifft. So zeigt Abb. 6, dass anfangs die fünf Lastwagen A, …, E leer und die drei Rampen R1, R2 und R3 frei sind. Jedes Quadrat repräsentiert ein parametrisiertes Ereignis; eine Belegung der Variablen x und y durch einen Lastwagen beziehungsweise eine Rampe macht es zu einem konkreten Ereignis. Das Modell in Abb. 6 fixiert fünf Lastwagen und drei Rampen. Mit Symbolen für Mengen von Objekten ermöglicht die Prädikatenlogik eine weitere Abstraktion: Die Konstantensymbole L und R in Abb. 7 können frei wählbar als Mengen LA von Lastwagen und RA von Rampen interpretiert werden. Anfangs treffen die Prädikate leere Lastwagen und freie Rampen auf die Elemente von LA und RA zu. Wie oben beschrieben, hat Petri stattdessen vorgeschlagen, eine Theorie der Informatik als Dynamisierung der Logik aufzubauen, mit lokaler Beschränktheit von Schritten als wesentlichem Konzept. Daraus folgt vielerlei; darunter das oben diskutierte Konzept nicht zeitlich, sondern kausal geordneter Abläufe. Obwohl Petris Ideen seit Langem vorliegen, sind sie nicht wirklich in allen Einzelheiten ausgearbeitet und kaum bekannt. Auch Publikationen zu Petrinetzen folgen oft klassischer Theoriebildung und weniger Petris Vorschlägen.
Abb. 6 Systemmodell für fünf Lastwagen und drei Rampen
Abb. 7 Schema für beliebig viele Lastwagen und Rampen
Abb. 8 Eintritt der Transition A fährt ran
Es stellt sich die Frage, ob wir eine Informatik als (Rechen-)Technik haben wollen, wie beispielsweise den „Betonbau“ im Bauingenieurswesen, oder ob wir Informatik als Wissenschaft entwickeln wollen, mit einer universellen Theorie diskreter Systeme nach dem Vorbild der Physik. Carl Adam Petri hat dafür vor 60 Jahren einiges vorgeschlagen. Im Rückblick erweist sich die Konzentration auf Software und Programmiersprachen als zu kurz gesprungen. Der Übergang von traditionellen kontinuierlichen zu diskreten Modellen verlangt eine gründlichere theoretische Fundierung, die die klassische Automatentheorie nicht leistet.
Eine gute Modellierungstechnik integriert die Beschreibung von Verhalten, Objekten und Daten sowie Methoden zur Komposition und Verfeinerung von Modulen. Vorschläge, wie das konkret aussehen kann, finden sich im Deep Dive.
Deep Dive
Petri, Carl Adam (1977), Non-Sequential Processes. Gesellschaft für Mathematik und Datenverarbeitung.
Fettke, Peter und Reisig, Wolfgang (2024), Understanding the Digital World. Springer-Verlag.
Die Fachgruppe für Petrinetze und verwandte Systemmodelle, die Fachgruppe Modellierung betrieblicher Informationssysteme sowie der Querschnittsausschuss Modellierung betrachten das Thema Modellierung aus verschiedenen Perspektiven.
