Zum Inhalt springen

Petri-Netz

aus Wikipedia, der freien Enzyklopädie

Als Petri-Netze werden Modelle diskreter, vorwiegend verteilter Systeme bezeichnet. Der Informatiker Carl Adam Petri hat sie in den 1960er Jahren ausgehend von endlichen Automaten entwickelt, zunächst noch nicht in der heute gebräuchlichen Form. Dabei hat Petri nach grundlegenden Prinzipien zur Beschreibung nebenläufiger Schaltvorgänge gesucht, die später zu axiomatischen Theorien der Nebenläufigkeit verdichtet wurden.

Heutzutage werden Varianten von Petri-Netzen nicht nur in der Informatik zur Modellierung verwendet, sondern z. B. auch in der theoretischen Biologie, bei Geschäftsprozessen, im Maschinenbau, der Logistik und vielen anderen Gebieten. Viele andere Modellierungstechniken wie z. B. Aktivitätsdiagramme der UML 2 haben Prinzipien der Petri-Netze übernommen.

Allgemeine Symbolik und Beschreibung

In der Grundausführung stellt sich ein Netz als ein Graph dar, der aus zwei Arten von Knoten aufgebaut ist, die Stellen (oder auch Plätze) bzw. Transitionen genannt werden. Die Knoten sind durch gerichtete Kanten verbunden, wobei eine Kante genau eine Stelle mit einer Transition oder umgekehrt verbindet. Ursprünglich hat Petri ungetypte Knoten betrachtet. Ein Netz mit solchen Knoten wird als Stellen/Transitions-Netz (kurz: S/T-Netz bzw. P/T-Netz aus dem Englischen zurückübersetzt als Platz/Transitions-Netz) bezeichnet.

Später wurden Netze mit durch Marken getypten Knoten und somit Attributen zu den Knoten eingeführt, welche als Prädikate an Transitionen und Kanten ausgewertet werden. Ein Netz mit Marken und dadurch getypten Knoten wird daher Prädikat/Transitions-Netz genannt, wobei die englischsprachige Bezeichnung Coloured Petri Net (CPN) – gefärbtes Petri-Netz – mindestens genauso häufig anzutreffen ist. Die Stellen können mit beliebig vielen Marken belegt sein. Eine solche Markierung stellt einen verteilten Zustand des Systems dar.

Die Dynamik eines Netzes ergibt sich aus dem Schalten von Transitionen: schaltet eine Transition, so entnimmt sie Marken aus den Stellen in ihrem unmittelbaren Vorbereich und legt Marken in die Stellen in ihrem Nachbereich, und zwar jeweils so viele, wie an den Kanten angegeben ist. Solange die Transition mehr Marken benötigt, als tatsächlich dort liegen, kann sie noch nicht schalten.

Mathematische Darstellung eines Petri-Netzes

Ein P/T-Netz kann als ein Quintupel <math>(P,T,F,W,m_0)</math> dargestellt werden, dabei ist

  • <math>P\cap T = \emptyset</math> (Disjunktheit) und <math>P\cup T \neq\emptyset</math>
  • <math>P</math> die (in aller Regel endliche) Menge der Stellen
  • <math>T</math> die (ebenfalls endliche) Menge der Transitionen
  • <math>F\subseteq\left(P\times T\right)\cup\left(T\times P\right)</math> die Flussrelation, die die Kanten angibt. Kanten verbinden also stets Stellen mit Transitionen oder andersherum, niemals Stellen mit Stellen oder Transitionen mit Transitionen.
  • <math>W\colon F\to\mathbb{N}</math> die Kantengewichtungsfunktion, erweitert auf <math>W'\colon \left(P\times T\right)\cup\left(T\times P\right)\to\mathbb{N}_0</math> durch <math>(a,b)\notin F\Leftrightarrow W'(a,b) = 0</math>
  • <math>m_0 \colon P \to\mathbb{N}_0</math> die Anfangsmarkierung
Datei:Seasons 1.svg
Abb. 0a: Vier-Jahreszeiten-Netz (1)

Die Dynamik der Netze wird im nächsten Abschnitt erläutert.

Dynamik der Petri-Netze

Datei:Petrinet transition example.svg
Beispiel: Schalten einer Transition

Um die Dynamik und weitere Eigenschaften von Petri-Netzen zu beschreiben, sind folgende Definitionen und Bezeichnungen hilfreich.

Vor- und Nachbereich

Der Vorbereich von <math>x \in P \cup T</math>, bezeichnet mit <math>\bullet x </math>, ist die Menge aller Knoten, von denen eine Kante zum Knoten <math>x</math> führt: <math>\bullet x = \{y| (y,x) \in F\}</math>.

Der Nachbereich von <math>x \in P \cup T</math>, bezeichnet mit <math> x \bullet</math>, ist die Menge aller Knoten, zu denen eine Kante vom Knoten <math>x</math> aus führt: <math>x \bullet = \{y| (x,y) \in F\}</math>.

Beim Schalten einer Transition <math>t</math> wird aus jeder Stelle <math>p_v \in \bullet t</math> des Vorbereichs der Transition eine Anzahl an Marken entnommen und in jede Stelle <math> p_n \in t \bullet </math> des Nachbereichs der Transition eine Anzahl an Marken hinzugefügt. Die Anzahl der hinzugefügten bzw. entnommenen Marken jeder Stelle <math>p_i</math> richtet sich nach dem Gewicht der Kante zwischen der Transition und der Stelle <math>p_i</math>.<ref name="Abel90">Dirk Abel: Petri-Netze für Ingenieure. Modellbildung und Analyse diskret gesteuerter Systeme. Springer, Berlin u. u. 1990, ISBN 3-540-51814-2.</ref>

Schaltregel

Die Schaltregel in P/T-Netzen stellt sich wie folgt dar: Eine Transition <math>t \in T</math> kann aus einer Markierung <math>m</math> schalten (notiert <math> m \stackrel{t}{\rightarrow} </math>) und das Netz in den Zustand <math>m'</math> bringen, genau dann, wenn die Schaltbedingung für <math>t</math> erfüllt ist für alle Stellen <math>p \in \bullet t</math> (<math>t</math> ist dann aktiviert bzw. schaltfähig):

  • <math>0 \leq m(p) - W(p,t)</math>

und die Folgemarkierung <math>m'(p)</math> für alle Stellen <math>p \in P</math> erfüllt ist:

  • <math>m'(p) = m(p) - W'(p,t) + W'(t,p)</math>.

Das Schalten der aktivierten Transition <math>t</math> ergibt also die neue Markierung <math>m'</math>. Man schreibt dann <math>m \stackrel{t}{\rightarrow}m'</math>.

Schaltsequenz und Erreichbarkeit

Eine Folge von Transitionen <math>\sigma = t_1, t_2, ..., t_n </math> mit <math> t_i \in T </math> heißt Schaltfolge oder Schaltsequenz. Kann eine Schaltfolge auf eine Markierung <math>m</math> angewendet werden, so dass bei jedem Schritt die Schaltbedingung erfüllt ist, so heißt die Schaltsequenz anwendbar auf <math>m</math>. Ob eine Schaltfolge anwendbar ist oder wie eine bestimmte Markierung erreicht werden kann, ergibt das Erreichbarkeitsproblem. Gibt es eine anwendbare Schaltfolge <math>\sigma</math>, die die Anfangsmarkierung <math>m_0</math> in <math>m</math> überführt, so ist die Markierung <math>m</math> erreichbar. Die Menge aller erreichbaren Markierungen <math>R_N(m_0)</math> wird Erreichbarkeitsmenge genannt.<ref name="Abel90" />

Durch die Schaltregel ergibt sich, nach Art einer operationalen Semantik, ein vielleicht unendlicher beschrifteter Graph mit Wurzel <math>m_0</math>, der Erreichbarkeitsgraph, aus dem alle möglichen Schaltfolgen und damit einhergehenden Zustandsänderungen des Netzes abgelesen werden können. Es ist allerdings zu beachten, dass dies noch keine echt nebenläufige Semantik ist, da von jeder nebenläufigen Ereignismenge nur die Sequentialisierungen als Schaltfolgen betrachtet werden können.

Das Vier-Jahreszeiten-Netz <math>N_1</math> aus Abbildung 0a hat aufgrund seiner sehr simplen Struktur einen sehr einfachen Erreichbarkeitsgraphen, der ebenso wie <math>N_1</math> vier Zustände hat und vier Übergänge, die genau den Transitionen entsprechen.

Datei:Seasons 2.svg
Abb. 0b: Erweitertes Vier-Jahreszeiten-Netz

Das Netzbeispiel aus Abbildung 0b hat dagegen doppelt so viele erreichbare Zustände, da unabhängig von der Jahreszeit der Sack Reis umgefallen sein kann oder auch nicht. Dieses Netz zeigt auch die Eignung von Petri-Netzen zum Darstellen verteilter Zustände und kausal unabhängiger, „nebenläufiger“ Ereignisse in verschiedenen Teilen des Systems – „In China fällt ein Sack Reis um“ und „a“ können unabhängig voneinander schalten, da sie weder eine gemeinsame Vorbedingung haben noch eines vom anderen abhängt.

Modellieren mit Petri-Netzen

Für Petri-Netze sind ganz unterschiedliche Varianten und Ausprägungen vorgeschlagen worden. In den 1960er und 1970er Jahren wurden zunächst elementare Varianten untersucht; heutzutage werden oft „high-level“-Formen verwendet. Sie sind formal aufwendiger, beschreiben aber das modellierte System intuitiv genauer und unmittelbarer.

Einführendes Beispiel {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri1.png
Abb. 1: abstraktes Modell der Aktion eines Keksautomaten

Als einführendes Beispiel eines High-level-Netzes zeigt Abb. 1 ein von Einzelheiten weitestgehend abstrahierendes Modell eines Keksautomaten: Im Anfangszustand befindet sich eine Münze im Eingabeschlitz des Automaten. Damit kann der Automat einen Schritt durchführen: Er kassiert die Münze und legt eine Keksschachtel in das Ausgabefach. So entsteht der Endzustand.

Datei:Petri2.png
Abb. 2: Modell des Inneren des Keksautomaten

Abbildung 2 verfeinert und erweitert das Modell in seinem Anfangszustand, indem nun das Verhalten des Inneren des Automaten sichtbar wird, zusammen mit der möglichen Rückgabe der eingeworfenen Münze.

Komponenten von Petri-Netzen {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Der genaue Sinn der Abbildungen 1 und 2 folgt aus den universellen Modellierungsprinzipien von Petri-Netzen: In einem (gegebenen oder geplanten diskreten) System identifiziert man eine Reihe von Komponenten, die im Petri-Netz-Modell explizit dargestellt werden. Dazu gehören:

  • Speicherkomponenten, die Gegenstände oder Datenelemente enthalten können (im Beispiel: Eingabeschlitz, Entnahmefach, Kasse, Signalplatz, Keksspeicher, Rückgabe) und denen Bedingungen zugeordnet werden. Im Modell werden sie als Plätze bezeichnet und graphisch als Kreise oder Ellipsen dargestellt;
  • Aktivitäten, die Speicherinhalte verändern können (in Abb. 1: t, in Abb. 2: a, b, c). Alle Aktivitäten werden unbedingt nach Schalten der Plätze ausgeführt. Im Modell werden sie als Transitionen bezeichnet und graphisch als Quadrat oder Rechteck dargestellt.
  • Zustände, also wechselnde Verteilungen von Gegenständen oder Datenelementen in Speicherkomponenten. (Abb. 2 beschreibt einen Zustand mit einer Münze im Eingabeschlitz und 3 Keksschachteln im Keksspeicher. Alle anderen Speicherkomponenten sind leer.) Im Modell bildet eine Verteilung von Marken auf die Plätze eine Markierung mit Bedingungen. Graphische Darstellungen (wie die in Abb. 1 und Abb. 2) zeigen üblicherweise die Anfangsmarkierung, die den Anfangszustand des Systems beschreibt.
  • Gegenstände oder Datenelemente, die im System vorkommen, d. h. erzeugt, transformiert und verbraucht werden (im Beispiel: Münzen, Keksschachteln und Signale). Im Modell werden sie als Marken bezeichnet und graphisch möglichst „intuitiv“ dargestellt.
  • Übergänge von Zuständen in neue Zustände als Beschreibung der Zustandswechsel: (im Beispiel: der Übergang vom Anfangs- zum Endzustand in Abb. 1 und vom Anfangs- zu einem Zwischenzustand in den Abbildungen Abb. 2 und Abb. 3). Im Modell kann man solche Schritte intuitiv als „Fluss von Marken durch die Kanten“ auffassen.

Schritte {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri3.png
Abb. 3: nach Eintritt von a

Von einer gegebenen Markierung <math>M</math> eines Petri-Netz-Modells aus ist eine neue Markierung <math>M'</math> erreichbar, indem eine Transition <math>t</math> eintritt. Dazu muss <math>t</math> in <math>M</math> aktiviert sein. <math>t</math> ist in <math>M</math> aktiviert, wenn jeder bei <math>t</math> endende Pfeil an einem Platz <math>p</math> beginnt, der eine Marke enthält, die am Pfeil selbst notiert ist. In Abb. 1 ist t also aktiviert; in Abb. 2 sind a und c aktiviert, nicht aber b. Wenn eine aktivierte Transition <math>t</math> eintritt, verschwinden die oben beschriebenen Marken von ihren Plätzen, und für jeden bei <math>t</math> beginnenden Pfeil <math>f</math> entsteht gemäß seiner Anschrift eine Marke auf dem Platz, wo <math>f</math> endet.

Auf diese Weise entsteht in Abb. 1 aus der Anfangsmarkierung durch Eintritt von t die Endmarkierung. Aus Abb. 2 entsteht durch Eintritt von a die in Abb. 3 gezeigte Markierung.

Die „abstrakte“ Marke (schwarzer Punkt) auf dem Signal-Platz von Abb. 3 aktiviert nun zusammen mit einer Keksschachtel im Speicher die Transition b. Indem b eintritt, erscheint schließlich eine Keksschachtel im Entnahmefach. In Abb. 2 ist auch die Transition c aktiviert. Tritt c (statt a) ein, entsteht eine Markierung mit einer Münze in Rückgabe.

Mit der obigen Regel zum Eintritt von Transitionen sieht man unmittelbar, dass <math>2</math> oder <math>3</math> Münzen im Einwurfschlitz zu entsprechend vielen Schachteln im Entnahmefach führen. Mit einer zweiten Münze im Einwurfschlitz kann die Transition a unmittelbar nach ihrem ersten Eintritt wiederum eintreten, unabhängig vom (ersten) Eintritt von b.

Das Verhalten verteilter Systeme {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Das obige Beispiel zeigt vielfältige Bezüge zwischen den Aktivitäten eines verteilten Systems. Dementsprechend kann der Eintritt zweier Transitionen in unterschiedlicher Weise zusammenhängen. In Abb. 2 beispielsweise:

nichtdeterministisch
a und c treten alternativ zueinander ein. Die Münze im Einwurfschlitz aktiviert die beiden Transitionen a und c. Indem eine von beiden eintritt, ist die andere nicht mehr aktiviert. Welche der beiden Transitionen eintritt, wird nicht modelliert.
geordnet
a tritt vor b ein: Um einzutreten, benötigt b eine Marke, die a vorher erzeugt hat.
nebenläufig
Nachdem – wie in Abb. 3 – a eingetreten ist, kann mit einer zweiten Münze im Einwurfschlitz (in Abb. 2 nicht dargestellt) a ein zweites (oder c ein erstes) Mal eintreten, nebenläufig zum (d. h. unabhängig vom) Eintritt von b.

Elementare Netze {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri4.png
Abb. 4: elementare Fassung des Keksautomaten

Abbildung 4 zeigt ein Petri-Netz-Modell des Keksautomaten, in dem die Marken für Münzen, Signale und Keksschachteln nicht unterschieden werden: Alle werden gleichermaßen als „schwarze“ Marken dargestellt. Dabei tragen Pfeile keine Inschrift (nach der Systematik der Abbildungen 1 bis 3 müsste jeder Pfeil mit „<math>\bullet</math>“ beschriftet sein). In dieser Form sind Petri-Netze in den 1960er Jahren entstanden und häufig als Platz-/Transitionsnetze bezeichnet worden.<ref name="Baumgarten96">Bernd Baumgarten: Petri-Netze. Grundlagen und Anwendungen. 2. Auflage. Spektrum – Akademischer Verlag, Heidelberg u. a. 1996, ISBN 3-8274-0175-5.</ref><ref name="Reisig10">Wolfgang Reisig: Petri-Netze. Modellierungstechnik, Analysemethoden, Fallstudien. Vieweg + Teubner, Wiesbaden 2010, ISBN 978-3-8348-1290-2.</ref> Die Regeln zum Eintritt einer Transition <math>t</math> sind in diesem Fall besonders einfach: <math>t</math> ist aktiviert, wenn jeder bei <math>t</math> endende Pfeil bei einem Platz beginnt, der mindestens eine Marke enthält. Diese Marken verschwinden beim Eintritt von <math>t</math> und es entsteht eine neue Marke auf jedem Platz, an dem ein bei <math>t</math> beginnender Pfeil endet.

Datei:Petri5.jpg
Abb. 5: wechselseitiger Ausschluss

Solche einfachen Marken sind intuitiv angemessen, wenn (verteilter) Kontrollfluss modelliert wird, wie beispielsweise im Schema des wechselseitigen Ausschlusses in Abb. 5: Jeder der beiden Prozesse <math>l</math> und <math>r</math> („links“ und „rechts“) durchläuft zyklisch die drei Zustände lokal, wartend, kritisch. Der Schlüssel sorgt dafür, dass niemals beide Prozesse zugleich kritisch sind. In diesem Beispiel trägt jeder Platz immer entweder keine oder eine Marke. Man kann jeden Platz daher als eine Bedingung auffassen, die gelegentlich erfüllt und gelegentlich unerfüllt ist. Solche Netze werden häufig als Bedingungs-/Ereignisnetze bezeichnet.

Analyse von Petri-Netzen

Eigenschaften von Petri-Netz-Modellen {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Wichtige Eigenschaften eines Systems sollten sich in seinem Modell widerspiegeln. Ein Petri-Netz muss daher nicht nur Verhalten, sondern auch Eigenschaften eines Systems darstellen. Beispielsweise hat in den Netzen der Abbildungen 2, 3 und 4 jede erreichbare Markierung <math>M</math> die Eigenschaft

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

<math>M(\mathsf{Kasse})+ M(\mathsf{Speicher})= 3+M(\mathsf{Signal}).</math>

Dabei bezeichnet <math>M(p)</math> für einen Platz <math>p</math> die Anzahl der Marken auf <math>p</math> in der Markierung <math>M</math>. Für jede Münze in der Kasse ist also eine Keksschachtel abgegeben worden oder (mit einer Marke auf Signal) wird noch abgegeben. Entsprechend gilt für Abb. 5

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

<math>M(\mathsf{kritisch}_l)+ M(\mathsf{kritisch}_r)\leq 1.</math>

Es ist also immer höchstens ein Prozess in seinem kritischen Zustand. Eine naheliegende, aber schon für elementare Systemnetze überraschend komplizierte Fragestellung ist die Erreichbarkeit einer beliebig gewählten Markierung <math>M</math>:

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

<math>\text{Ist}\ M\ \text{von der Anfangsmarkierung aus erreichbar?}</math>

Es hat Jahre gedauert, bis dafür ein Algorithmus gefunden und somit die Entscheidbarkeit dieses Erreichbarkeitsproblems nachgewiesen wurde.<ref>Ernst W. Mayr: An algorithm for the general Petri net reachability problem. In: SIAM Journal on Computing. Bd. 13, Nr. 3, 1984, S. 441–460, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref> Weitere wichtige Eigenschaften eines elementaren Systemnetzes <math>N</math> sind:

  • <math>N</math> terminiert: Jede in der Anfangsmarkierung beginnende anwendbare Schaltsequenz von <math>N</math> erreicht irgendwann einen Deadlock, d. h. eine Markierung, die keine Transition aktiviert. Diese Markierung heißt tot (die Keksautomaten terminieren).
  • <math>N</math> ist deadlockfrei: In <math>N</math> sind keine Deadlocks erreichbar (der wechselseitige Ausschluss ist deadlockfrei).
  • <math>N</math> ist lebendig: Von jeder erreichbaren Markierung aus ist für jede Transition <math>t</math> eine Markierung erreichbar, die <math>t</math> aktiviert (der wechselseitige Ausschluss ist lebendig).
  • <math>N</math> ist schwach lebendig: Zu jeder Transition <math>t</math> von <math>N</math> gibt es eine erreichbare Markierung, die <math>t</math> aktiviert (Keksautomat und wechselseitiger Ausschluss sind beide schwach lebendig).
  • <math>N</math> ist <math>k</math>-beschränkt für eine Zahl <math>k</math>: Jeder Platz enthält unter jeder erreichbaren Markierung höchstens <math>k</math> Marken (der Keksautomat ist 3-beschränkt, der wechselseitige Ausschluss ist 1-beschränkt). Ein 1-beschränktes Petri-Netz heißt sicher.
  • <math>N</math> ist reversibel: Die Anfangsmarkierung ist von jeder erreichbaren Markierung aus erreichbar (der wechselseitige Ausschluss ist reversibel).
  • <math>N</math> hat einen Homestate: Ein Homestate von <math>N</math> ist eine Markierung, die von jeder erreichbaren Markierung aus auf jeden Fall erreicht wird. Weder der Keksautomat noch der wechselseitige Ausschluss hat einen Homestate.

Zu beachten ist, dass die Eigenschaften Lebendigkeit, Beschränktheit und Reversibilität unabhängig voneinander sind.<ref>Tadao Murata: Petri nets: Properties, Analysis and Applications. In: Proceedings of the IEEE. Bd. 77, Nr. 4, April 1989, S. 541–580, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref>

Außerdem gelten folgende Sätze:

  • <math>N</math> ist genau dann beschränkt, wenn seine Erreichbarkeitsmenge <math>R(N, m_0)</math> endlich ist.
  • Ein Kausalnetz <math>N</math> ist genau dann nicht beschränkt, wenn es eine Transition <math>t \in T</math> mit <math>\bullet t = \emptyset</math> und <math>t \bullet \neq \emptyset</math> gibt, d. h. eine Transition, zu der keine Kante führt, aber von der mindestens eine Kante zu einer Stelle führt.
  • Jedes lebendige und beschränkte Petri-Netz ist stark zusammenhängend.
  • Eine gewöhnliche Zustandsmaschine <math>N</math> ist genau dann lebendig, wenn sie stark zusammenhängend ist und <math>m_0</math> nicht der Nullvektor ist, d. h. mindestens eine Marke im Netz ist.
  • Ein Kausalnetz <math>N</math> ist genau dann lebendig, wenn es keine Stelle <math>s \in S</math> mit <math>\bullet s = \emptyset</math> und <math>s \bullet \neq \emptyset</math> gibt, d. h. keine Stelle, zu der keine Kante führt, aber von der mindestens eine Kante zu einer Transition führt.
  • Ein gewöhnlicher Synchronisationsgraph <math>N</math> ist genau dann lebendig, wenn es in jedem gerichteten Kreis in <math>N</math> mindestens eine Stelle <math>s \in S</math> mit <math>m_0(s) > 0</math> gibt, d. h. jeder Kreis enthält mindestens eine Marke.
  • Das Erreichbarkeitsproblem ist entscheidbar.
  • Für jedes Petri-Netz ist es entscheidbar, ob es lebendig ist.<ref name=":0">Jürgen Dassow, Otto-von-Guericke-Universität Magdeburg: Petri-Netze</ref>

Nachweis von Eigenschaften

Bei allen beschriebenen Eigenschaften stellt sich die Frage, wie man sie für ein gegebenes anfangsmarkiertes Netz beweist oder widerlegt (vgl. Verifikation). Alle genannten Eigenschaften sind für elementare Netze entscheidbar, allerdings nur mit Algorithmen, deren Komplexität für die Praxis viel zu groß ist. In der Praxis werden deshalb Algorithmen für hinreichende oder notwendige Bedingungen verwendet. Diese Algorithmen beruhen auf Platzinvarianten, anfangsmarkierten Fallen, der Markierungsgleichung und dem Überdeckungsgraphen eines Systemnetzes.

Erreichbarkeit

Datei:Two-boundedness-ub.png
Einfaches Petri-Netz
Datei:Reachability graph for petri net.png
Erreichbarkeitsgraph für das oben dargestellte Petri-Netz

Das Erreichbarkeitsproblem für Petri-Netze besteht darin, für ein gegebenes Petri-Netz <math>N</math> und eine Markierung <math>m</math> zu entscheiden, ob <math>m \in R(N)</math>. Es geht darum, den oben definierten Erreichbarkeitsgraphen so lange zu durchlaufen, bis die gesuchte Markierung erreicht ist oder nicht mehr gefunden werden kann. Dies kann schwierig sein, denn der Erreichbarkeitsgraph ist im Allgemeinen unendlich, und es ist nicht einfach zu bestimmen, wann ein sicherer Abbruch möglich ist. Es wurde bewiesen, dass das Erreichbarkeitsproblem entscheidbar ist.<ref name=":0" /> Es wurden Arbeiten veröffentlicht, die sich mit effizienten Lösungsansätzen befassen.<ref>{{#invoke:Vorlage:Literatur|f}}</ref> Im Jahr 2018 verbesserten Czerwiński et al. die untere Schranke und zeigten, dass das Erreichbarkeitsproblem nicht in der Komplexitätsklasse ELEMENTARY liegt.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux, Filip Mazowiecki|Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux, Filip Mazowiecki: }}{{#if:|{{#if:The Reachability Problem for Petri Nets is Not Elementary|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=The Reachability Problem for Petri Nets is Not Elementary}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://arxiv.org/abs/1809.07115%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=The Reachability Problem for Petri Nets is Not Elementary}}}}|[{{#invoke:URLutil|getNormalized|1=http://arxiv.org/abs/1809.07115}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=The Reachability Problem for Petri Nets is Not Elementary}}}}]}}{{#if:| ({{{format}}}{{#if:2019-04-11{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://arxiv.org/abs/1809.07115%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://arxiv.org/abs/1809.07115}}%7C%7C}}}}{{#if:The Reachability Problem for Petri Nets is Not Elementary|{{#if:{{#invoke:WLink|isValidLinktext|1=The Reachability Problem for Petri Nets is Not Elementary|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: 2019-04-11|,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2019-04-11| {{#if:{{#invoke:DateTime|format|2019-04-11|noerror=1}}
            |{{#invoke:DateTime|format|2019-04-11|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2019-04-11|class=Zitationswartung}} }}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2019-04-11|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:90461||(?)}}}}}}{{#if: 2026-04-03|;}}}}{{#if: 2026-04-03| {{#if:2019-04-11{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2026-04-03 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2026-04-03|class=Zitationswartung}} }} {{#invoke:DateTime|format|2026-04-03|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:2019-04-11{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2019-04-11{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/1809.07115
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/1809.07115
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/1809.07115}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/1809.07115 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/1809.07115
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/1809.07115}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/1809.07115 }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/1809.07115
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/1809.07115
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/1809.07115}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/1809.07115 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/1809.07115
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/1809.07115}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/1809.07115 }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> Im Jahr 2021 wurde unabhängig voneinander von Jerome Leroux<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Jérôme Leroux|Jérôme Leroux: }}{{#if:|{{#if:The Reachability Problem for Petri Nets is Not Primitive Recursive|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=The Reachability Problem for Petri Nets is Not Primitive Recursive}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://arxiv.org/abs/2104.12695%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=The Reachability Problem for Petri Nets is Not Primitive Recursive}}}}|[{{#invoke:URLutil|getNormalized|1=http://arxiv.org/abs/2104.12695}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=The Reachability Problem for Petri Nets is Not Primitive Recursive}}}}]}}{{#if:| ({{{format}}}{{#if:2021-09-02{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://arxiv.org/abs/2104.12695%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://arxiv.org/abs/2104.12695}}%7C%7C}}}}{{#if:The Reachability Problem for Petri Nets is Not Primitive Recursive|{{#if:{{#invoke:WLink|isValidLinktext|1=The Reachability Problem for Petri Nets is Not Primitive Recursive|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: 2021-09-02|,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2021-09-02| {{#if:{{#invoke:DateTime|format|2021-09-02|noerror=1}}
            |{{#invoke:DateTime|format|2021-09-02|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2021-09-02|class=Zitationswartung}} }}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2021-09-02|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:90461||(?)}}}}}}{{#if: 2026-04-03|;}}}}{{#if: 2026-04-03| {{#if:2021-09-02{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2026-04-03 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2026-04-03|class=Zitationswartung}} }} {{#invoke:DateTime|format|2026-04-03|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:2021-09-02{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2021-09-02{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/2104.12695
       | {{#if:  | [3] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/2104.12695
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.12695}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/2104.12695 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/2104.12695
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.12695}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/2104.12695 }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/2104.12695
       | {{#if:  | [4] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/2104.12695
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.12695}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/2104.12695 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/2104.12695
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.12695}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/2104.12695 }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> sowie von Wojciech Czerwiński und Łukasz Orlikowski<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Wojciech Czerwiński, Łukasz Orlikowski|Wojciech Czerwiński, Łukasz Orlikowski: }}{{#if:|{{#if:Reachability in Vector Addition Systems is Ackermann-complete|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Reachability in Vector Addition Systems is Ackermann-complete}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://arxiv.org/abs/2104.13866%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Reachability in Vector Addition Systems is Ackermann-complete}}}}|[{{#invoke:URLutil|getNormalized|1=http://arxiv.org/abs/2104.13866}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Reachability in Vector Addition Systems is Ackermann-complete}}}}]}}{{#if:| ({{{format}}}{{#if:2022-10-25{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}} 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://arxiv.org/abs/2104.13866%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://arxiv.org/abs/2104.13866}}%7C%7C}}}}{{#if:Reachability in Vector Addition Systems is Ackermann-complete|{{#if:{{#invoke:WLink|isValidLinktext|1=Reachability in Vector Addition Systems is Ackermann-complete|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: 2022-10-25|,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2022-10-25| {{#if:{{#invoke:DateTime|format|2022-10-25|noerror=1}}
            |{{#invoke:DateTime|format|2022-10-25|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2022-10-25|class=Zitationswartung}} }}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2022-10-25|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:90461||(?)}}}}}}{{#if: 2026-04-03|;}}}}{{#if: 2026-04-03| {{#if:2022-10-25{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2026-04-03 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2026-04-03|class=Zitationswartung}} }} {{#invoke:DateTime|format|2026-04-03|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:2022-10-25{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2022-10-25{{#if: 2026-04-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/2104.13866
       | {{#if:  | [5] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/2104.13866
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.13866}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/2104.13866 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/2104.13866
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.13866}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/2104.13866 }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://arxiv.org/abs/2104.13866
       | {{#if:  | [6] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://arxiv.org/abs/2104.13866
      | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.13866}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://arxiv.org/abs/2104.13866 Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://arxiv.org/abs/2104.13866
       | {{#if:{{#invoke:URLutil|isWebURL|http://arxiv.org/abs/2104.13866}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://arxiv.org/abs/2104.13866 }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> gezeigt, dass dieses Problem Ackermann-vollständig und somit nicht primitiv-rekursiv ist.

Obwohl die Erreichbarkeit ein geeignetes Werkzeug zur Erkennung fehlerhafter Zustände zu sein scheint, weist der konstruierte Graph in praktischen Problemen meist viel zu viele Zustände auf, um sie zu berechnen. Um dieses Problem zu beheben, wird üblicherweise lineare temporale Logik in Verbindung mit dem Baumkalkül verwendet, um zu beweisen, dass solche Zustände nicht erreichbar sind. Die lineare temporale Logik nutzt die Semi-Entscheidungstechnik, um zu prüfen, ob ein Zustand tatsächlich erreichbar ist. Dazu werden notwendige Bedingungen für das Erreichen des Zustands ermittelt und anschließend bewiesen, dass diese Bedingungen nicht erfüllt werden können.

Softwarewerkzeuge

Seit den 1980er-Jahren entstand eine Vielzahl unterschiedlicher Softwarewerkzeuge zur Erstellung und zur Analyse von Petri-Netzen. Als universelles Werkzeug für High-level-Netze hat sich insbesondere das Werkzeug CPN Tools durchgesetzt.<ref name="JensenKristensen09">Kurt Jensen, Lars M. Kristensen: Coloured Petri Nets. Modelling and Validation of Concurrent Systems. Springer, Berlin u. u. 2009, ISBN 978-3-642-00283-0.</ref> Daneben gibt es eine Vielzahl spezifischer Werkzeuge für spezielle Netzvarianten, beispielsweise zur Analyse zeitbehafteter und stochastischer Netze<ref name="PetriWorld">The Petri Net World</ref> oder für spezielle Anwendungsbereiche, beispielsweise service-orientierter Architekturen.<ref name="servicetechnology09" />

Verallgemeinerungen, Spezialfälle, Varianten

Die allgemeinste Form von High-level-Netzen {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri6.jpg
Abb. 6: Variante des Keksautomaten

Das Modell des Keksautomaten in (Abb. 1 – Abb. 3) ist ein Beispiel eines high-level Netzes. Die volle Ausdrucksstärke solcher Netze erreicht man mit Hilfe von Variablen und Funktionen in den Inschriften der Pfeile. Als Beispiel modelliert Abb. 6 eine Variante des Keksautomaten mit 4 Münzen im Eingabeschlitz. Für die 4. Münze gibt es keine Schachtel im Speicher; die Münze soll also auf jeden Fall zurückgegeben werden. Dazu enthält Abb. 6 einen Zähler, deren Marke die Anzahl verfügbarer Schachteln angibt. Die Transition a wird aktiviert, indem die Variable x den aktuellen Wert dieser Marke annimmt. Zusätzlich ist a mit der Bedingung x > 0 beschriftet, die zum Eintritt von a erfüllt sein muss. Damit reduziert jeder Eintritt von a den Zählerwert um 1 und a ist beim Wert 0 nicht mehr aktiviert. Jede weitere Münze landet dann also über c in der Rückgabe.

Spezialfall free-choice {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri7.png
Abb. 7: Die free-choice Eigenschaft

Im Modell des Keksautomaten der Abbildungen 2, 3 und 4 wählt die Marke im Einwurfschlitz nichtdeterministisch eine der Transitionen a oder c. Diese Wahl hängt von keinen weiteren Vorbedingungen ab; sie ist frei.

Im System des wechselseitigen Ausschlusses aus Abb. 5 hat der Schlüssel die Wahl zwischen den Transitionen b und e. Diese Wahl hängt aber zusätzlich davon ab, dass auch <math>\mathsf{wartend}_l</math> und <math>\mathsf{wartend}_r</math> markiert sind. Sie ist nicht frei.

Ein Netz <math>N</math> ist ein Free-choice-Netz, wenn schon seiner Struktur nach alle Wahlmöglichkeiten frei sind, falls also für zwei Pfeile, die am selben Platz <math>p</math> beginnen, gilt: Sie enden an Transitionen, an denen keine weiteren Pfeile enden.<ref name="DeselEsparza95">Jörg Desel, Javier Esparza: Free Choice Petri Nets (= Cambridge Tracts in Theoretical Computer Science. Bd. 40, 1995). Cambridge University Press, Cambridge u. a. 1995, ISBN 0-521-46519-2.</ref> Abbildung 7 skizziert diese Bedingung. Offensichtlich sind alle Modelle des Keksautomaten Free-choice-Netze, nicht aber der wechselseitige Ausschluss in Abb. 5.

Ob eine der in oben beschriebenen Eigenschaften gilt oder nicht gilt, ist für Free-choice-Netze mit effizienten Algorithmen entscheidbar.<ref name="DeselEsparza95" />

Verallgemeinerungen elementarer Netze {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Petri8.png
Abb. 8: Kantengewichte und Platzkapazitäten:<math>t</math> ist nicht aktiviert

Schon in den 1970er Jahren wurden elementare Netze um zahlreiche weitere Ausdrucksmittel ergänzt. Drei davon seien hier geschildert:

  • Pfeile gewichten: Jedem Pfeil ist als „Gewicht“ eine natürliche Zahl <math>n</math> zugeordnet. Bei Eintritt der mit dem Pfeil verbundenen Transition fließen dann <math>n</math> Marken (statt nur einer Marke) durch den Pfeil.
  • Die Kapazität der Plätze beschränken: Jedem Platz <math>p</math> wird als „Schranke“ eine natürliche Zahl <math>n</math> zugeordnet. Wenn beim Eintritt einer Transition <math>t</math> mehr als <math>n</math> Marken auf <math>p</math> entstehen würden, ist <math>t</math> nicht aktiviert. Abbildung 8 zeigt ein Beispiel.
  • Einen Platz auf Abwesenheit von Marken testen: Ein Platz <math>p</math> ist mit einer Transition <math>t</math> durch eine neuartige „Inhibitor“-Kante verbunden. <math>t</math> ist nicht aktiviert, wenn <math>p</math> eine oder mehrere Marken trägt. Abbildung 9 skizziert diese Konstruktion.
Datei:Petri9.png
Abb. 9: Wirkung einer Inhibitorkante

Gewichtete Pfeile und kapazitätsbeschränkte Plätze steigern nicht wirklich die Ausdruckskraft: Man kann sie mit intuitiv plausiblen Mitteln simulieren. Hingegen kann man mit Inhibitorkanten tatsächlich mehr ausdrücken und konsequenterweise weniger entscheiden. Insbesondere ist die Erreichbarkeit für Netze mit Inhibitorkanten nicht entscheidbar.<ref name="Reutenauer90">Christophe Reutenauer: The mathematics of Petri nets. Prentice-Hall International, Hemel Hempstead 1990, ISBN 0-13-561887-8.</ref> Weitere Ausdrucksmittel sind gelegentlich erforderlich, um wirklich genau zu modellieren, wie sich ein verteiltes System verhält. Beispielsweise wollen wir im System des wechselseitigen Ausschlusses in Abb. 5 darstellen, dass jeder der beiden Prozesse für immer in seinem lokalen Zustand, aber nicht für immer in seinem kritischen Zustand verharren darf. Dazu unterscheiden wir die kalte Transition a („tritt nicht unbedingt ein, wenn sie aktiviert ist“) von der heißen Transition b („tritt ein, wenn sie aktiviert ist“). Mit den Transitionen b und e ist es noch komplizierter: Wenn wir jedem wartenden Prozess garantieren möchten, dass er irgendwann einmal kritisch wird, müssen wir Fairness für b und e verlangen. Mit dem Unterschied zwischen heißen und kalten Transitionen und mit der Forderung von Fairness kann man die Menge der „gemeinten“ Abläufe eines Petri-Netzes sehr viel genauer charakterisieren.<ref name="Reisig10" />

Zeitbehaftete und stochastische Netze {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Wenn Transitionen geordnet eintreten, in Abb. 2 beispielsweise erst a dann b, soll diese Ordnung kausal und nicht zeitlich interpretiert werden. Dann ist es konsequent, in Abb. 2 mit einer zweiten Münze im Eingabeschlitz das erste Eintreten von b und das zweite Eintreten von a als unabhängig voneinander aufzufassen und nicht als gleichzeitig.

Dennoch gibt es Systeme mit Aktionen, deren Dauer modelliert werden soll, oder die in irgendeiner Weise an Uhren orientiert sind. Zur Modellierung solcher Systeme wurden zahlreiche Varianten zeitbehafteter Petri-Netze vorgeschlagen. Dabei werden Plätze, Transitionen, Marken und Pfeile mit Zeitstempeln und Zeitintervallen versehen. Diese Zusätze regeln die Aktivierung von Transitionen und erzeugen neue Zeitstempel nach dem Eintritt einer Transition.

Wenn zwei Transitionen <math>t</math> und <math>u</math> um dieselbe Marke einer Markierung <math>M</math> konkurrieren (beispielsweise konkurrieren in Abb. 5 b und e um die Marke auf Schlüssel) und wenn <math>M</math> immer wieder erreicht wird, will man gelegentlich modellieren, dass <math>t</math> mit der Wahrscheinlichkeit <math>p</math> und <math>u</math> mit der Wahrscheinlichkeit <math>1-p</math> eintritt. Dafür eignet sich die breit ausgebaute Theorie der stochastischen Netze.<ref name="Marsanetal95">Marco Ajmone Marsan, Gianfranco Balbo, Gianni Conte, Susanna Donatelli, Giuliana Franceschinis: Modelling with Generalized Stochastic Petri Nets. Wiley, Chichester u. a. 1995, ISBN 0-471-93059-8.</ref>

Höhere Petri-Netze

Um Systeme, die mobile Komponenten als Teilsysteme enthalten, einheitlich zu beschreiben, wurden Petri-Netz-Formalismen entwickelt, bei denen die Marken wiederum als Netzinstanzen interpretiert werden. Bei diesen sogenannten Netzen in Netzen sind etliche Semantik-Varianten möglich, die sich unter anderem hinsichtlich der Frage unterscheiden, ob Marken als Netzexemplare oder lediglich als Referenzen zu verstehen sind.

Diese Formalismen entspringen einer objektorientierten Betrachtungsweise, bei der Exemplare von Klassen (Netzmustern) erzeugt werden können und eine Kommunikation zwischen Objekten über definierte Schnittstellen möglich ist.

Einige der frühen Vertreter sind die Objekt-Petri-Netze von Lakos<ref name="Lakos95">Charles Lakos: From coloured Petri nets to object Petri nets. In: Giorgio De Michelis, Michel Diaz (Hrsg.): Application Theory of Petri Nets 1995. 16th International Conference Turin, Italy, June 26–30, 1995. Proceedings (= Lecture Notes in Computer Science. 935). Springer, Berlin u. a. 1995, ISBN 3-540-60029-9, S. 278–297.</ref> (heute angesichts intensiver Weiterentwicklung hauptsächlich von historischer Bedeutung) und Valk, der diese zusammen mit Jessen<ref name="Jessen">Eike Jessen, Rüdiger Valk: Rechensysteme. Grundlagen der Modellbildung (= Studienreihe Informatik.). Springer, Berlin u. a. 1987, ISBN 3-540-16383-2.</ref> ursprünglich im Kontext von Auftragssystemen einführte.

Die historische Entwicklung

Der Anfang {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Die Forschung zu Petri-Netzen begann mit der Dissertation von Carl Adam Petri im Jahr 1962.<ref name="Petri62">Carl Adam Petri: Kommunikation mit Automaten (= Schriften des Rheinisch-Westfälischen Institutes für Instrumentelle Mathematik an der Universität Bonn. 2, {{#if: {{#if: | {{#invoke:TemplUtl|faculty|{{{suffix}}}}} }} 

 | {{#if:trim|405247-x}}. In: Zeitschriftendatenbank (ZDB).
 | {{#if: {{#if:  | {{#invoke:TemplUtl|faculty|{{{kurz}}}}} }}
     |
     | ZDB-ID 
   }}405247-x

}}{{#if: {{#invoke:TemplUtl|faculty|}} | | {{#if: {{#invoke:URIutil|isDNBvalid|405247-x|ZDB}} | | ZDB-ID ungültig{{#ifeq: 0 | 0 | }}}}}}). Mathematisches Institut der Universität Bonn, Bonn 1962, (Zugleich: Darmstadt, Technische Hochschule, Dissertation, 1962).</ref> Diese Arbeit wurde zunächst kaum beachtet; die Theoretische Informatik hat damals andere Fragestellungen verfolgt und für die Praxis kamen Petris Vorschläge zu früh. Ein erster Durchbruch im Bereich der Theorie kam Ende der 1960er-Jahre mit der Verwendung von Petris Ideen im Project MAC des MIT. In den 1970er Jahren wurden Platz-/Transitionsnetze weltweit studiert, allerdings recht oft aus dem verengten Blickwinkel formaler Sprachen.<ref name="Peterson81">James L. Peterson: Petri Net Theory and the Modeling of Systems. Prentice-Hall, Englewood Cliffs NJ 1981, ISBN 0-13-661983-5.</ref>

Die Entwicklung seit den 1980er-Jahren {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Seit Beginn der 1980er Jahre wurden ganz unterschiedliche Varianten von High-level-Netzen vorgeschlagen, die Gegenstände, Datenelemente oder Symbole als Marken verwenden. Diese Formalismen erhöhen die Ausdruckskraft von Platz-/Transitionsnetzen beträchtlich. Zugleich konnten viele Analysetechniken von Platz-/Transitionsnetzen auf diese Formalismen verallgemeinert werden.<ref name="Reisig10" />

Mit zunehmendem Interesse an verteilten Systemen und verteilten Algorithmen wurden und werden seit den 1980er-Jahren zahlreiche neue Modellierungstechniken vorgeschlagen. Petri-Netze haben sich gegenüber diesen Neuentwicklungen behauptet; vielfach werden sie als Maßstab für die Qualität und die Ausdrucksmächtigkeit für Modelle verteilter Systeme verwendet. Einen Überblick über zahlreiche Anwendungsbereiche von Petri-Netzen gibt.<ref name="GiraultValk03">Claude Girault, Rüdiger Valk: Petri Nets for Systems Engineering. A Guide to Modeling, Verification, and Applications. Springer, Berlin u. a. 2003, ISBN 3-540-41217-4.</ref>

Aktuelle Themen {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Mit Petri-Netzen werden heutzutage Systeme modelliert, deren Verhalten aus diskreten, lokal begrenzten Schritten besteht. Das sind oft Systeme, die Rechner integrieren oder die mit Rechnern simuliert werden. Zu den derzeit besonders viel versprechenden Anwendungen von Petri-Netzen gehört die Modellierung von Prozessen der Systembiologie,<ref name="Kochetal11">Ina Koch, Wolfgang Reisig, Falk Schreiber (Hrsg.): Modeling in Systems Biology. The Petri Net Approach (= Computational Biology. 16). Springer, London u. u. 2011, ISBN 978-1-84996-473-9.</ref> der Geschäftsprozesswelt<ref name="Aalstetal">Wil van der Aalst, Christian Stahl: Modeling Business Processes. A Petri Net-Oriented Approach. The MIT Press, Cambridge MA u. a. 2011, ISBN 978-0-262-01538-7.</ref> und der Service-orientierten Architekturen.<ref name="servicetechnology09">www.service-technology.org.</ref>

Anwendungen

Fertigungsprozesse

Die Vorteile der Verwendung von Petri-Netzen zur Modellierung von Fertigungsprozessen sind vielfältig. Ihre Vielseitigkeit beruht auf ihrer Universalität. Beispielsweise können sie zur Modellierung des Betriebs technischer Komponenten in der Produktion, von Hardware- und Softwareprozessen, wirtschaftlichen Faktoren, die intelligente Fertigungsprozesse beeinflussen, eingesetzt werden. Das Konzept der intelligenten Fertigung umfasst verschiedene Systemebenen umfasst, die gemäß dem ISA-95-Standard klassifiziert sind.

Produktionssysteme bestehen aus vielen Elementen. Je nach Branche können dies beispielsweise Roboter, Maschinen, Förderbänder, Lager und andere sein. Diese Elemente verfügen über eine eigene Betriebslogik, um die Produktion zu unterstützen und zu ermöglichen. Diese Logik wird in den Zuständen des Petri-Netzes abgebildet.

Ein generisches Basiselement für eine Maschine kann beispielsweise zwei Zustände haben: „Leerlauf“ und „Ausgelastet“. Abhängig von der Komplexität der Aufgabe, die eine Maschine ausführen muss, kann ihr Zustandsraum weiter ausgearbeitet werden, um beschreibendere Zustände einzuschließen, die während der Produktion gesteuert oder beobachtet werden müssen. So kann man eine Maschine zunächst als einfaches Petri-Netz darstellen, das nur diese beiden Zustände „Leerlauf“ und „Ausgelastet“ enthält. Diese können dann erweitert werden, um zusätzliche Details über die Maschine zu modellieren. Bei der Modellierung eines Fertigungsprozesses kann das Modell in mehrere Ströme unterteilt werden. Diese Ströme enthalten auch die entsprechenden Übergangstypen im Petri-Netz, welche die Zustandsänderungen des Systems in Abhängigkeit von der Ausführung bestimmter Operationen oder Ereignisse beschreiben. Diese Zerlegung ermöglicht somit eine detailliertere Analyse und Steuerung einzelner Elemente des Produktionsprozesses und verbessert dessen Effizienz und Vorhersagbarkeit.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Logistik

Zeitgesteuerte farbige Petri-Netze eignen sich hervorragend zur Beschreibung logistischer Prozesse. Ein logistisches System besteht aus physikalisch verteilten Teilsystemen mit einer komplexen Interaktionsstruktur und ist somit ein typisches Beispiel für ein diskretes dynamisches System. Zweitens haben jüngste Entwicklungen im Bereich der Logistik die Steuerung logistischer Prozesse verkompliziert. Die Integration logistischer Aktivitäten führt häufig zu komplexen Steuerungsproblemen. Daher besteht Bedarf an einem integrierten Rahmenwerk für die Modellierung und Analyse logistischer Systeme.

Oft wird die Problemstellung vereinfacht, um analytische Lösungen zu ermöglichen. Aus diesem Grund sind viele Ergebnisse in diesem Bereich nicht allgemein anwendbar und erfordern die Beratung durch einen Experten. Beispiele hierfür sind die Anwendung von Warteschlangennetzen auf Terminplanungsprobleme und die Anwendung linearer Programmierung auf die Transportplanung. Obwohl diese Analysemethoden helfen, Einblicke in das Problem zu gewinnen, sind sie nur in recht spezifischen Situationen anwendbar. Darüber hinaus beschreiben einige der in diesem Bereich berichteten Ergebnisse Techniken für Probleme, die in der Praxis gar nicht existieren. Ein Forschungszweig konzentriert sich auf praktische Logistikprobleme. Die Ergebnisse sind oft qualitativer und informeller Natur. Die in diesem Bereich verwendeten Ansätze sind hauptsächlich disziplinorientiert, d. h. sie konzentrieren sich auf einen spezifischen Aspekt der Logistik. Beispiele hierfür sind die Forschung zu Kundenservice, Lagertechnik, Kommunikationseinrichtungen und Personalbedarf.<ref>Wil van der Aalst: Timed coloured Petri nets and their application to logistics</ref>

Anwendungsgebiete

Siehe auch

Normen und Standards

  • ISO/IEC 15909-1: Software und System-Engineering – Höhere Petri-Netze – Teil 1: Begriffe, Definitionen und grafische Notation (zurzeit nur in Englisch verfügbar)
  • ISO/IEC 15909-2: Software und System-Engineering – Höhere Petri-Netze – Teil 2: Transferformat (zurzeit nur in Englisch verfügbar)

Weblinks

Literaturverweise

<references />

{{#ifeq: s | p | | {{#if: 4045388-1 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: s | p | | {{#if: 4045388-1 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: s | p | {{#if: 4045388-1 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: s | p | {{#if: 4045388-1 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: s | p | {{#if: | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: s | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: s | p | {{#if: | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: s | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Petri-Netz&oldid=90461“