„Über Petri-Netze mit inhibitor-Kanten…“ Anhang B (OCR)

Rainer A. Stawarz1. Juli 2026Allgemein

💡 OCR-Versionen können vom Original abweichen 💡

Anhang B. LITERATURVERZEICHNIS

[1] T. Araki, T. Kasami, Decidable Problems on the Strong Connectivity of Petri Net Reachability Sets, Theoret. Comp. Sci. 4 (1977) 99-119.

[2] H.G. Baker, Rabin’s Proof of the Undecidability of the Reachability Set Inclusion Problem of Vector Addition Systems, MIT Project MAC, CSGM 79, Cambridge, Mass. (1973).

[3] H. Kleine-Büning, T. Lettmann, E.W. Mayr, Projections of Vector Addition System Reachability Sets Are Semilinear, Theoret. Comp. Sci. 64 (1989) 343-350.

[4] E.W. Cardoza, Computational Complexity of the Word Problem for Commutative Semigroups, MAC Technical Memorandum 67, M.I.T. (1975).

[5] F. Commoner, Deadlocks in Petri Nets, Applied Data Research, Wakefield MA, CA 7206-3211 (1972), Applied Data Research Inc.

[6] J. Grabowski, The Decidability of Persistence for Vector Addition Systems, IPL, 11 (1980) 20-23.

[7] M. Hack, Decidability Questions for Petri Nets, MIT, LCS, TR 161, Cambridge, Mass. (1976).

[8] M. Hack, Petri Nets and Commutative Semigroups, MIT Project MAC, CSGN 18, Cambridge, Mass. (1974).

[9] M. Hack, The Equality Problem for Vector Addition Systems is Undecidable, C.S.G. Memo 121, Project MAC, M.I.T. (1975).

[10] J. Hopcroft, J.J. Pansiot, On the Reachability Problem for 5-Dimensional Vector Addition Systems, Theoret. Comp. Sci. 8 (1979) 135-159.

[11] R. Karp, R. Miller, Parallel Program Schemata, J. Comp. Syst. Sci. 3 (1969) 147-195.

[12] R.M. Keller, Vector Replacement Systems: a Formalism for Modelling Asynchronous Systems, Princeton Univ., Princeton, NJ, CSL, TR 117 (1972).

[13] S.R. Kosaraju, Decidability of Reachability in Vector Addition Systems, Proc. 14th Ann. ACM STOC (1982) 267-281.

[14] K. Lautenbach, Exakte Bedingungen der Lebendigkeit für eine Klasse von Petri-Netzen, GMD Bonn (St. Augustin), Bericht Nr. 82 (1973).

[15] R. Lipton, The Reachability Problem is Exponential-Space Hard, Dept. Computer Science Rep. 62, Yale Univ., New Haven, CT (1976).

[16] E.W. Mayr, An Algorithm for the General Petri Net Reachability Problem, SIAM J. Comput. 13,3 (1984) 441-460.

[17] E.W. Mayr, Persistence of Vector Replacement Systems is Decidable, Acta Informatica 15 (1981) 309-318.

[18] E.W. Mayr, A.R. Meyer, The Complexity of the Finite Containment Problem for Petri Nets, Journal of the Association for Computing Machinery, Vol 28, No. 1 (1981) 561-576.

[19] E.W. Mayr, A.R. Meyer, The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals, Advances in Mathematics 46,3 (1982) 305-329.

[20] H. Müller, Decidability of Reachability in Persistent Vector Replacement Systems, Proc. 9th Symposium on MFCS (1980), LNCS 88, Springer, New York, 426-438.

[21] C.A. Petri, Kommunikation mit Automaten, Institut für Instrumentelle Mathematik, Bonn, Schriften des IMM Nr. 2 (1962).

[22] M. Presburger, Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes-Rendus du I. Congrès des Mathématiciens des pays, Warsaw (1930) 92-101.

[23] G. Sacerdote, L. Tenney, The Decidability of the Reachability Problem for Vector Addition Systems, Proc. 9th Ann. ACM STOC (1977) 61-76.

[24] D.C. Oppen, A 2^{2^2ⁿ} Upper Bound on the Complexity of Presburger Arithmetic, J. Comput. Systems Sci. 16 (1978) 323-332.

[25] J. Van Leeuwen, A Partial Solution to the Reachability Problem for Vector Addition Systems, Sixth Ann. ACM Symp. on the Theory of Computing (1974) 303-309.

„Über Petri-Netze mit inhibitor-Kanten, deren Leistungsfähigkeit und Erreichbarkeitsmengen“, Rainer A. Stawarz @ J.W. Goethe-Universität Frankfurt/M, Diplomarbeit (1991)

Rainer A. Stawarz30. Juni 2026Allgemein

„Über Petri-Netze mit inhibitor-Kanten, deren Leistungsfähigkeit und Erreichbarkeitsmengen“

Rainer A. Stawarz @ J.W. Goethe Universität Frankfurt/M
Diplomarbeit (1991) ⇒ Original

INHALTSVERZEICHNIS

§1. HISTORISCHES, MOTIVATION (5-8)

Petri-Netze und deren Bedeutung in der Systemanalyse, systemanalytische Entsprechung des Erreichbarkeitsproblems, Bekanntes hinsichtlich des Gleichheits- und Inklusionsproblems, Beschreibungsproblem der Erreichbarkeitsmengen, Grenzen der Anwendbarkeit der gewöhnlichen Petri-Netze, WPNC-Berechenbarkeit, inhibitor-Kanten und deren Auswirkung auf die Entscheidbarkeit der Schlüsselprobleme, einfache (semilineare) Erreichbarkeitsmengen, bekannte Grenzen der Semilinearität, Motivation und Inhaltsüberblick.

§2. GRUNDLEGENDE KONZEPTE (9–22)

Gewöhnliche Petri-Netze, Transitionsfolgen, Schaltfolgen, Schaltpfade, kontrollierende Stellen, Erreichbarkeitsmengen und deren Schlüsselprobleme, Vektor-Ersetzungssysteme, Test- und Ersetzungsvektoren, Vektor-Additionssysteme, Translationsvektoren, Petri-Netze mit inhibitor-Kanten, Vektor-Additions- und Ersetzungssysteme mit inhibitor-Vektoren, Beispiele.

§3. SIMULATION VON VARIANTEN DES GRUNDMODELLS (23–34)

Petri-Netze mit kontrollierenden Zuständen, Projektionen der Erreichbarkeitsmengen, Simulation der kontrollierenden Stellen und Zustände in Vektor-Additionssystemen und Vektor-Ersetzungssystemen, begrenzte Simulierbarkeit von inhibitor-Kanten, Aufwand der Simulation, Beispiele.

§4. SEMILINEARE ERREICHBARKEITSMENGEN (35–42)

§5. DIMENSIONSBEZOGENE SEMILINEARITÄTSGRENZEN (43–72)

Auswirkungen der kontrollierenden Stellen und Zustände sowie inhibitor-Kanten auf dimensionsbezogene Semilinearitätsgrenzen, dimensionsbezogene Semilinearitätsgrenzen und Algorithmen zur Berechnung von Erreichbarkeitsmengen für zweidimensionale Vektor-Additionssysteme und Vektor-Ersetzungssysteme mit kontrollierenden Zuständen und verschiedener Anzahl von inhibitor-Kanten, sowie für vierdimensionale und gewöhnliche Vektor-Ersetzungssysteme, Bedeutung von inhibitor-Stellen, weitere Semilinearitätsgrenzen.

§6. WPNC-BERECHENBARKEIT, ZÄHLERAUTOMATEN (73–82)

Schwache Petri-Netz Computer, WPNC-Berechenbarkeit der Addition, Multiplikation, Exponentialfunktion u. a., Subtraktion, Modulo-Division und die Notwendigkeit von inhibitor-Kanten für deren WPNC-Berechenbarkeit, Zählerautomaten, Minsky-Barsdin-Theoreme, Konsequenzen.

§7. OFFENE FRAGEN, DISKUSSION (83–88)

WPNC-Klassen, These über einfachste Petri-Netze mit nicht-semilinearen Erreichbarkeitsmengen und daraus resultierende dimensionsbezogene Semilinearitätsgrenzen, Satz über schwach-monotone inhibitor-Transitionen, Invarianz der Semilinearität unter schwach-monotonen inhibitor-Transitionen.

Anhang A – SIMULATION DER KONTROLLIERENDEN ZUSTÄNDE IN GEWÖHNLICHEN VEKTOR-ADDITIONSSYSTEMEN (89–94)

Anhang B – LITERATURVERZEICHNIS (95–98)

„Über Petri-Netze mit inhibitor-Kanten…“ §1 (OCR)

Rainer A. Stawarz29. Juni 2026Allgemein

💡 OCR-Versionen können vom Original abweichen 💡

§1. HISTORISCHES, MOTIVATION

Petri-Netze (konzipiert 1962 durch C. A. Petri [21]) liefern ein sehr komfortables und mittlerweile kaum wegzudenkendes Hilfsmittel bei der Darstellung und Analyse verschiedenartiger Vorgänge. Insbesondere die systemanalytischen Aspekte im Zusammenhang mit interaktiv ablaufenden Prozessen, wie z. B. Synchronisation (locking), Systemstillstand (deadlock), Objektverfügbarkeit (scheduling) können in einer sehr anschaulichen Form angegangen werden [5], [12]. Die zu den Petri-Netzen äquivalenten algebraischen Aggregate, wie Vektor-Additions- bzw. Ersetzungssysteme¹ erleichtern zudem die rechnergestützte Simulation von derartigen Interaktionen.

Die naturgemäß schwierigen systemanalytischen Probleme, wie z. B. Aspekte der Lebendigkeit eines vorliegenden Systems [7], [14], werden in Anlehnung an das Petri-Netz-Modell zwar anschaulicher, aber selbstverständlich nicht leichter. So sind beispielsweise Fragen im Zusammenhang mit den Erreichbarkeitsmengen² von Petri-Netzen häufig gar nicht algorithmisch entscheidbar – und wenn, dann meistens extrem komplex. Andere wiederum konnten bislang weder als entscheidbar noch als unentscheidbar ausgewiesen werden.

Andererseits sollte nicht übersehen werden, dass die in [21] vorgestellten Gebilde, die wir im weiteren als „gewöhnliche Petri-Netze“ bezeichnen wollen, nicht uneingeschränkt universell sind. An die Grenzen deren Anwendbarkeit stößt man z. B. beim Simulieren von Berechnungsvorgängen. Die durch Rabin konzipierte schwache Berechenbarkeit durch ein (gewöhnliches) Petri-Netz (angelehnt an das WPNC-Modell³), gilt nur für eine bestimmte Klasse von Funktionen. Zwar sind sogar einige stark wachsende Funktionen in diesem Sinne berechenbar (z. B. die Ackermann-Funktion – [18]), aber bereits bei relativ simplen, nicht monoton wachsenden Funktionen entsteht die Notwendigkeit, das Feuern von Transitionen an das Leersein von bestimmten Stellen zu knüpfen. Das so modifizierte Petri-Netz enthält sog. inhibitor-Kanten und ist nur eine der inzwischen zahlreichen Varianten des Grundmodells. Andere enthalten z. B. Stellen mit eingeschränkten Aufnahmekapazitäten oder verzweigte Kanten – um nur einige zu nennen [27]. Diese Modifikationen machen aber die o. e. Probleme, z. B. das Erreichbarkeitsproblem, offensichtlich nicht leichter, denn die WPNC-Berechenbarkeit von hinreichend komplizierten Funktionen (z. B. notwendigerweise auf der Basis von Petri-Netzen mit inhibitor-Kanten) ist gleichbedeutend mit entsprechend diffizilen Erreichbarkeitsmengen, mit allen Konsequenzen für die damit zusammenhängenden Probleme. So modifizierte Petri-Netze sind demnach zwar leistungsfähiger, können aber die an sie angelehnte Systemanalyse erheblich erschweren oder gar unmöglich machen.

Diesen Sachverhalt beobachten wir anhand des sog. allgemeinen Erreichbarkeitsproblems⁴. Die Frage, ob ein gewisser Zustand von einem fixierten Anfangszustand aus erreicht werden kann, ist von essentieller Bedeutung für viele systemanalytische Aspekte (z. B. Erreichbarkeit eines Zustandes, der dem Systemstillstand entspricht [5] oder Systemlebendigkeit⁵ [14], [29]), sowie für viele Probleme aus dem Bereich der Algebra und Numerik. Dieses Problem ist entscheidbar, bezogen auf die gewöhnlichen Petri-Netze – unentscheidbar hingegen für Petri-Netze mit inhibitor-Kanten⁶ [7].

Interessant ist aber auch die Frage, wie schwer das Erreichbarkeitsproblem ist und wie es praktisch gelöst werden kann (hier denken wir stets an gewöhnliche Petri-Netze). Die naheliegende Vorgehensweise, dieses Problem durch Bestimmung der Erreichbarkeitsmenge zu lösen, ist überraschenderweise algorithmisch nicht realisierbar. Unentscheidbar ist auch die Frage der mengentheoretischen Inklusion bzw. Gleichheit von Erreichbarkeitsmengen zweier Petri-Netze (sog. Inklusions- bzw. Gleichheitsproblem⁷ [2], [9], [28]). So verwundert es nicht, dass die in [16], [26] vorgestellten Algorithmen keinerlei Aspekte der Erreichbarkeitsmengenbeschreibung angehen. Eine brauchbare Beschreibung der Erreichbarkeitsmengen ist nur bei den gegenüber dem Grundmodell etwas vereinfachten Petri-Netzen möglich [1], [6], [17], [20]. All das zeugt von ziemlicher Nähe zur Grenze des algorithmisch Machbaren, und es kann folglich davon ausgegangen werden, dass das Erreichbarkeitsproblem sehr komplex ist. Selbst bei paralleler Abarbeitung kommt man um exponentielle Laufzeiten nicht herum [15].

Die Unentscheidbarkeit des Inklusionsproblems und die darauf zurückgehenden enormen Schwierigkeiten bei der praktischen Lösung des (allgemeinen) Erreichbarkeitsproblems veranlassen uns zu fragen, unter welchen Umständen die unentscheidbaren Probleme entscheidbar, insbesondere das Erreichbarkeitsproblem einfacher werden kann. Wir haben bereits angedeutet, dass die Erreichbarkeitsmengen von gewissen Klassen der gewöhnlichen Petri-Netze berechnet werden können. Der Preis dafür ist eine gegenüber dem Grundmodell eingeschränkte Leistungsfähigkeit (bisher sprachen wir von leistungssteigernden Varianten des Grundmodells) – diese ist aber in der Praxis häufig ausreichend. Ein wichtiger Spezialfall liegt vor, wenn die Erreichbarkeitsmenge endlich ist, was sogar feststellbar ist [11]. Es ist nämlich in diesem Falle möglich, die Erreichbarkeitsmenge zu berechnen, und folglich ist das (endliche) Inklusionsproblem (und damit auch das Gleichheitsproblem) entscheidbar [11], wenn auch von exorbitanter Komplexität [18]. Auch unendliche Erreichbarkeitsmengen können berechenbar sein – vorausgesetzt, dass deren Struktur hinreichend regulär ist, z. B. semilinear, d. h. erfassbar durch die sog. Presburger-Arithmetik [22]. (Die Semilinearität der Erreichbarkeitsmenge ist ebenfalls algorithmisch feststellbar.)

Derartige Resultate können – neben der Vereinfachung vieler Probleme – auch eine andere Rolle spielen. Noch vor wenigen Jahren waren sie Teillösungen des damals noch offenen Erreichbarkeitsproblems und Meilensteine auf dem Wege zu dessen endgültigen Lösung. Gerade dieser Umstand war das Hauptmotiv für die Entstehung dieser Arbeit. Das bislang offene Erreichbarkeitsproblem von Petri-Netzen mit genau einer und dessen Unentscheidbarkeit bei mehreren inhibitor-Kanten haben uns veranlasst, nach ähnlichen Resultaten zu suchen. Insbesondere konzentrieren wir uns in der vorliegenden Arbeit auf die Frage, inwieweit die auf der Semilinearität basierenden Aussagen auf Petri-Netze mit inhibitor-Kanten übertragbar sind.

Die Semilinearität der Erreichbarkeitsmengen ist zunächst bei Petri-Netzen von geringer Dimension⁸ zu erwarten. Diese Vermutung bestätigte Van Leeuwen [25] für (gewöhnliche) Vektor-Additionssysteme der Dimension n ≤ 3, gefolgt von Hopcroft und Pansiot [10], die sogar die exakte, dimensionsbezogene Grenze der Semilinearität ermittelten von (n ≤ 5). In der vorliegenden Arbeit wird u. a. untersucht, ob inhibitor-Kanten diese Grenze tangieren. Unabhängig von der Dimension sind die Erreichbarkeitsmengen von sog. selbstdualen Petri-Netzen stets semilinear [4]. Das Erreichbarkeitsproblem ist in diesem Falle äquivalent zum Wortproblem kommutativer Halbgruppen⁹ [4], [8], und folglich ist dessen Komplexität von besonderem Interesse für uns [19].

Des Weiteren werden einige ergänzende Aussagen über die Struktur der Erreichbarkeitsmengen von gewöhnlichen Vektor-Ersetzungssystemen gemacht. Die hier ermittelte dimensionsbezogene Semilinearitätsgrenze gibt zugleich Aufschluss über das Kompaktierungspotential kontrollierender Stellen, die ein Bestandteil von Vektor-Ersetzungssystemen, nicht aber Vektor-Additionssystemen sind. Die Auswirkung solcher Stellen auf die dimensionsbezogene Semilinearitätsgrenze gewöhnlicher Petri-Netze wird damit ebenfalls geklärt. Die Kombination: kontrollierende Stellen und inhibitor-Kanten ist in diesem Zusammenhang etwas diffiziler und wird in der vorliegenden Arbeit nur im Sinne von oberen Schranken geklärt (ein möglicher Weg zur Beantwortung relevanter Fragen hinsichtlich dieser Konstellation wird durch eine entsprechend untermauerte These mit weiteren Hinweisen aufgezeichnet). Außerdem diskutieren wir Vektor-Additionssysteme, bei denen das Feuern von Transitionen zusätzlich an das Vorliegen eines bestimmten Zustandes geknüpft ist. Diese Gebilde sind leistungsfähiger und besitzen eine Semilinearitätsgrenze von n ≤ 2 [10]. Sog. Vektor-Ersetzungssysteme mit kontrollierenden Zuständen werden definiert und deren Semilinearitätsgrenze ermittelt. Auch hier wird die Auswirkung von inhibitor-Kanten auf diese Grenze untersucht, was uns ein Resultat liefert, das in Anbetracht der Minsky-Barsdin-Theoreme [30] zwar vermutet, jedoch nicht hergeleitet werden konnte.

Abschließend diskutieren wir einige offene Fragen, z. B. das Erreichbarkeitsproblem der Petri-Netze mit genau einer inhibitor-Kante. Ein interessanter Spezialfall geht auf schwach-monotone inhibitor-Transitionen zurück. Die Rückführung auf die Erreichbarkeitsmengen gewöhnlicher Petri-Netze ist wegen der Unentscheidbarkeit des Inklusionsproblems zwar noch nicht die abschließende Lösung des Erreichbarkeitsproblems, kann aber sicherlich als ein guter Tipp auf dem Wege dahin angesehen werden.

Die vorliegende Arbeit vermittelt Denkanstöße hinsichtlich vielerlei offener Probleme, z. B. hinsichtlich der Projektionen der Petri-Netz-Erreichbarkeitsmengen auf Stellen, um nur ein weiteres, bislang ungelöstes Problem zu nennen. Diese Projektionen sind bei gewöhnlichen Vektor-Additionssystemen unabhängig von der Dimension semilinear [3] – es ist allerdings unklar, wie viele inhibitor-Kanten diesen Sachverhalt verändern können.

______________________________

1. 1. engl. vector addition system, vector replacement system.
  2. diese entsprechen den Mengen aller erreichbaren Systemzustände.
  3. engl. weak Petri net Computer. Es handelt sich dabei um ganzzahlige Funktionen [16], [25].
  4. engl. general reachability problem.
  5. engl. liveness problem.
  6. bei zwei und mehr inhibitor-Kanten besteht Äquivalenz zum Halteproblem.
  7. engl. inclusion problem, equality problem.
  8. gemeint ist die Anzahl der Stellen.
  9. engl. word problem for commutative semigroups.

„Über Petri-Netze mit inhibitor-Kanten…“ Anhang A/B (orig.)

Rainer A. Stawarz29. Juni 2026Allgemein

AnhangAB

„Über Petri-Netze mit inhibitor-Kanten…“ §7

Rainer A. Stawarz29. Juni 2026Allgemein

Kap7

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§7. OFFENE FRAGEN. DISKUSSION.

Die abschließende Diskussion beginnen wir mit den zuletzt gemachten Beobachtungen hinsichtlich der WPNC-Berechenbarkeit. Die echten Inklusionen zwischen den Klassen WPNC, WPNC¹ und WPNC² sind sicherlich ein elegantes Resultat, das letzten Endes das belegt, was wir längst vermutet haben – nämlich, dass die Inhibitor-Kanten (und eine einzelne ebenfalls) eine qualitative Verstärkung des Grundmodells darstellen. Dennoch drängen sich dabei einige Fragen auf.

Die erste Frage wirft die ganzzahlige Division auf, die nur in einem ihrer Argumente fallend ist und trotzdem nicht WPNC¹-berechenbar zu sein scheint. Der Beweis für $|·/·| \in \text{WPNC}^1$ könnte uns dem bislang unbekannten Kriterium für die Zugehörigkeit von Funktionen zu den entsprechenden WPNC-Klassen näher bringen. Letzteres ist wohl die wichtigste offene Frage in diesem Zusammenhang.

Ein schwaches Kriterium haben wir im letzten Kapitel kennengelernt und zum Teil erfolgreich angewandt:

$\text{Anzahl der Inhibitor-Kanten} \ge \begin{cases} \text{Anzahl der Argumente, in denen die Funktion nicht wachsend ist.} \end{cases}$

Das Beispiel der ganzzahligen Division (und auch z. B. der Modulo-Division zur variablen Basis: $x \mod y \in \text{WPNC}^{2\,?}$ ) zeigt jedoch, dass dieses Kriterium nicht das exakte sein kann.

Aber auch einargumentige Funktionen werfen einige offene Probleme auf. Die Minsky-Barsdin-Theoreme (§6) definieren klar den dimensionsbezogenen Rahmen in Petri-Netzen, die wir als wettbewerbsfrei bezeichnet haben. Diese Eigenschaft könnte sich als hilfreich erweisen, wenn mehr bekannt wäre über obere Schranken z. B. hinsichtlich der kontrollierenden Zustände in den relevanten Zählerautomaten.

Die Theoreme 5.4 und 5.5 (§5) belegen, dass die Inhibitor-Kanten die dimensionsbezogenen Semilinearitätsgrenzen nur geringfügig verschieben. Auf der anderen Seite zeigt das Theorem 5.14 (zusammen mit dem Lemma 4.4), dass bereits genau eine Inhibitor-Kante eine solche Verschiebung verursacht. Dieser Umstand würde eher auf die Unentscheidbarkeit des bislang offenen Erreichbarkeitsproblems für Petri-Netze mit genau einer Inhibitor-Kante hindeuten.

Auf der anderen Seite lässt das Theorem 5.4 vermuten, dass die dimensionsbezogenen Semilinearitätsgrenzen für Petri-Netze ohne kontrollierende Zustände auf die Simulierbarkeit eines gewissen, in jeder Hinsicht „minimalen“ Netzes mit kontrollierenden Zuständen hinauslaufen. Diese These wird wohl kaum direkt beweisbar sein. Sie wird vielmehr aus den dimensionsbezogenen Semilinearitätsgrenzen für alle Grundmodell-Varianten folgen.

Zunächst müssen wir uns die Frage stellen, welche Petri-Netze (mit kontrollierenden Zuständen und nicht-semilinearen Erreichbarkeitsmengen) die einfachsten sind im Hinblick auf eine eventuelle Simulation. Ist vielleicht das Petri-Netz aus dem Beispiel Abb. 5 ein solch einfaches Petri-Netz (mit weniger als zwei Inhibitor-Kanten)? Diese Frage werden wir exakt beantworten können.

Auf diese These aufbauend zeigen wir, dass das Petri-Netz aus Abb. 5 in jeder Hinsicht das einfachste mit nicht-semilinearen Erreichbarkeitsmengen ist. Zunächst beobachten wir, dass mindestens zwei kontrollierende Zustände erforderlich sind. Eine zweite 0-Transition würde die kontrollierenden Zustände überflüssig machen. Es bleibt nur noch zu zeigen, dass sämtliche Transitionsbeschriftungen, die unser Petri-Netz beinhaltet, auch erforderlich sind.

Abb. 5

→ Hier Bild aus dem PDF einfügen

Damit wäre die Frage der dimensionsbezogenen Semilinearitätsgrenzen auf die Simulierbarkeit des Petri-Netzes aus Abb. 5 (oder eines anderen mit den gleichartigen Transitionsbeschriftungen) reduziert. Entscheidend ist dabei nicht nur die obige These, sondern auch das Theorem 5.4.

Tabellarische Zusammenfassung der Resultate (§5)

Gebilde	Inhibitor-Kanten Inhibitor-Stellen	Semilinearitätsgrenze Referenz
Vektor-Additions-/Ersetzungssysteme mit kontrollierenden Zuständen	ι = 0 σ = 0	n* = 2 Lemma 5.3, Abb. 5
Vektor-Additions-/Ersetzungssysteme mit kontrollierenden Zuständen	ι = 1 σ = 1	n* = 2 Theorem 5.4, Abb. 5
Vektor-Additions-/Ersetzungssysteme mit kontrollierenden Zuständen	ι ≥ 2 σ = 1	n* = 2 Theorem 5.5, Abb. 5
Vektor-Additions-/Ersetzungssysteme mit kontrollierenden Zuständen	ι ≥ 2 σ ≥ 2	n* = 1 Theorem 5.6, Abb. 9

„Über Petri-Netze mit inhibitor-Kanten…“ §6

Rainer A. Stawarz29. Juni 2026Allgemein

Kap6

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§6. WPNC-BERECHENBARKEIT, ZÄHLERAUTOMATEN

Im vorangegangenen Paragraphen haben wir die Auswirkungen von Inhibitor-Kanten auf dimensionsbezogene Semilinearitätsgrenzen studiert. Dennoch sind Inhibitor-Kanten ein Mittel, das qualitativ mehr ermöglicht als nur das Basismodell. Das zeigt sich insbesondere bei der Simulation von Berechnungsvorgängen.

Definition 6.1. (Schwacher Petri-Netz-Computer)

Sei $\mathcal{P}$ ein Petri-Netz mit Stellenmenge

$S = \{o\} \cup \{s\} \cup X \cup R$

mit $X = \{x_1, \dots, x_n\}$ und $R = \{r_1, \dots, r_k\}$ .

Für alle Transitionen $t \in T$ gelte:

$\kappa(o, t) = 0$
$\kappa(t, x_j) = 0$ für alle $x_j \in X$
$\kappa(t, s) \ge \kappa(s, t)$

Ein Petri-Netz $\mathcal{P}$ mit fester Initialmarkierung $m_1(R)$ ist ein schwacher Petri-Netz-Computer (kurz: $m_1(R)\text{-}WPNC$ ) für eine Funktion $f: D \to \mathbb{N}$ ( $D \subseteq \mathbb{N}^n$ ), wenn für alle zulässigen Anfangsmarkierungen $m_0$ mit $m_0(R) = m_1(R)$ , $m_0(s) = 1$ , $m_0(o) = 0$ und $m_0(X) \in D$ gilt:

$\{ m(o) \mid m_0 \to^* m \text{ und } m(x_2) = 0 \} = \{0, 1, \dots, f(m_0(X))\}.$

Existiert ein solches $WPNC$ für $f$ , dann heißt $f$ WPNC-berechenbar.

Beispiele

WPNC 1 (Addition)

$f(x_1, x_2) = x_1 + x_2$

Abbildung WPNC 1 (einfacher Addierer ohne innere Stellen)

→ Bild aus dem PDF hier einfügen

WPNC 2 (Multiplikation)

$f(x_1, x_2) = x_1 \cdot x_2$ mit fester Initialmarkierung $m_1(R) = (1,0,0,0)$

Abbildung WPNC 2

→ Bild aus dem PDF hier einfügen

WPNC 3 (Potenzierung)

$f(x) = x^a$ für festes $a \in \mathbb{N}$ (durch Kaskadierung von Multiplizierern)

Abbildung WPNC 3

→ Bild aus dem PDF hier einfügen

WPNC 4 (Exponentialfunktion)

$f(x) = 2^x$

Realisiert mit dem Petri-Netz aus Abb. 2 / Abb. 4 (Lemma 4.4). Es gilt stets:

$m(s_2) + \frac{m(s_3)}{2} \le 2^x$

Das Ergebnis wird aus $s_2$ und $s_3$ (mit Halbierung) entnommen.

Abbildung WPNC 4

→ Bild aus dem PDF hier einfügen

WPNC 5 (Subtraktion)

$f(x_1, x_2) = x_1 – x_2$ (für $x_1 \ge x_2$ )

Abbildung WPNC 5

→ Bild aus dem PDF hier einfügen

WPNC 6 (Modulo-Division)

$f(x) = x \mod a$ für festes $a \in \mathbb{N}$

Abbildung WPNC 6

→ Bild aus dem PDF hier einfügen

Weitere Ergebnisse zur WPNC-Berechenbarkeit

Alle monoton wachsenden Funktionen (inkl. Ackermann-Funktion) sind WPNC-berechenbar.
Nicht-monotone Funktionen wie Subtraktion, Division und Modulo sind mit gewöhnlichen Petri-Netzen nicht WPNC-berechenbar.
Mit einer Inhibitor-Kante werden Subtraktion und Modulo-Division berechenbar (WPNC 5 und WPNC 6).
Die ganzzahlige Division $\lfloor x_1 / x_2 \rfloor$ erfordert wahrscheinlich zwei Inhibitor-Kanten.

Es gilt die Inklusionskette:

$WPNC \subset WPNC^{1I} \subset WPNC^{2I}$

Zählerautomaten (Counter Automata)

Definition 6.2.

Ein n-Band Zählerautomat $CM^n = (Q, \chi)$ besteht aus einer endlichen Zustandsmenge $Q = \{q_1, \dots, q_m\}$ und einer Übergangsfunktion

$\chi : (Q \times \mathbb{N}^n) \to (Q \times \mathbb{Z}^n)$

mit der Eigenschaft:

$\chi(q, x) = \chi(q, x') \quad \text{falls die Nullstellenmengen von } x \text{ und } x' \text{ übereinstimmen}.$

Definition 6.3.

Eine Funktion $f \in \mathcal{F}$ ist CM³-berechenbar, wenn es einen 3-Band-Zählerautomaten gibt, der für jede Eingabe $x \in D$ in endlicher Zeit in einer Konfiguration mit $f(x)$ auf einem der Bänder hält.

Theorem 6.1 (Minsky)

Jede algorithmisch berechenbare Funktion $f : \mathbb{N} \to \mathbb{N}$ ist CM³-berechenbar.

Theorem 6.2 (Barsdin)

Für jede CM²-berechenbare Funktion $f$ existieren Konstanten $\phi, \omega \in \mathbb{N}$ , sodass gilt:

$f(x + m \omega) = f(x) + m \phi \quad \text{für alle } m = 0,1,2,\dots$

Korollar 6.3

Es gibt Funktionen aus $\mathcal{F}$ , die mit zweidimensionalen WPNCs (auch mit Inhibitor-Kanten und kontrollierenden Zuständen) nicht berechenbar sind.

Zusammenfassung

WPNCs können viele wichtige Funktionen berechnen, scheitern aber bei nicht-monotonen Funktionen ohne Inhibitor-Kanten.
Eine Inhibitor-Kante erweitert die Klasse deutlich (Subtraktion, Modulo).
Zählerautomaten sind äquivalent zu single-path Petri-Netzen mit Inhibitor-Kanten und kontrollierenden Zuständen.
Die Minsky-Barsdin-Theoreme geben untere Schranken für die Kompaktheit von Berechnungsmodellen.

Die Frage nach der minimalen Dimension und der minimalen Anzahl von Inhibitor-Kanten für die Berechnung beliebiger Funktionen aus $\mathcal{F}$ bleibt für das nächste Kapitel offen.

„Über Petri-Netze mit inhibitor-Kanten…“ §5

Rainer A. Stawarz29. Juni 2026Allgemein

Kap5

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§5. DIMENSIONSBEZOGENE SEMILINEARITÄTSGRENZEN

Das Korollar 4.5 markiert Dimensionen verschiedener Varianten von Petri-Netzen, in denen die Erreichbarkeitsmengen nicht-semilinear sein können. Die zentrale Frage lautet: Bis zu welcher Dimension ist Semilinearität der Erreichbarkeitsmengen obligatorisch?

Wir sprechen von einer dimensionsbezogenen Semilinearitätsgrenze $n^*$ , wenn die Semilinearität für alle Petri-Netze einer Klasse bis zur Dimension $n^*$ gilt und es in der Dimension $n^* + 1$ Gegenbeispiele mit nicht-semilinearen Erreichbarkeitsmengen gibt.

Lemma 5.1 (zitiert aus [10])

Die dimensionsbezogene Semilinearitätsgrenze für gewöhnliche Vektor-Additionssysteme mit kontrollierenden Zuständen beträgt $n^* = 2$ . Es gilt:

$\mathcal{R}_\mathcal{V}(\vec{M}_0) \in \text{sem}(\mathbb{N}^2 \times Q) \quad \text{für alle } \vec{M}_0 \in \text{sem}(\mathbb{N}^2 \times Q).$

Diese Erreichbarkeitsmengen sind effektiv berechenbar.

Lemma 5.2 (zitiert aus [10])

Die dimensionsbezogene Semilinearitätsgrenze für gewöhnliche Vektor-Additionssysteme ohne kontrollierende Zustände beträgt $n^* = 5$ . Es gilt:

$\mathcal{R}_\mathcal{V}(M_0) \in \text{sem}(\mathbb{N}^5) \quad \text{für alle } M_0 \in \text{sem}(\mathbb{N}^5).$

Diese Erreichbarkeitsmengen sind effektiv berechenbar.

Lemma 5.3

Die dimensionsbezogenen Semilinearitätsgrenzen für gewöhnliche Vektor-Additionssysteme und Vektor-Ersetzungssysteme mit kontrollierenden Zuständen sind gleich und betragen $n^* = 2$ . Es gilt:

$\mathcal{R}_\mathcal{V}(\vec{M}_0) \in \text{sem}(\mathbb{N}^2 \times Q) \quad \text{für alle } \vec{M}_0 \in \text{sem}(\mathbb{N}^2 \times Q).$

Theorem 5.4

Die dimensionsbezogenen Semilinearitätsgrenzen für gewöhnliche Vektor-Additionssysteme und Vektor-Ersetzungssysteme mit kontrollierenden Zuständen und genau einer Inhibitor-Kante betragen $n^* = 2$ . Es gilt:

$\mathcal{R}_\mathcal{V}(\vec{M}_0) \in \text{sem}(\mathbb{N}^2 \times Q) \quad \text{für alle } \vec{M}_0 \in \text{sem}(\mathbb{N}^2 \times Q).$

Diese Erreichbarkeitsmengen sind effektiv berechenbar.

Beweisidee (Algorithmus A1)

Der Algorithmus A1 berechnet die Erreichbarkeitsmenge auf der Inhibitor-Hyperebene $\eta‘$ rekursiv. Er kombiniert die Inhibitor-Translation mit dem Algorithmus aus [10].

Es wird gezeigt (Lemma 5.4.1), dass der Algorithmus in endlicher Zeit terminiert, und (Lemma 5.4.2), dass er die korrekte Menge auf der Hyperebene liefert.

Theorem 5.5

Die dimensionsbezogenen Semilinearitätsgrenzen für Systeme mit kontrollierenden Zuständen, beliebig vielen Inhibitor-Kanten und genau einer Inhibitor-Stelle betragen $n^* = 2$ . Es gilt:

$\mathcal{R}_{\mathcal{V},k}(\vec{M}_0) \in \text{sem}(\mathbb{N}^2 \times Q) \quad \text{für alle } \vec{M}_0 \in \text{sem}(\mathbb{N}^2 \times Q).$

Beweis durch Induktion über die Anzahl der Inhibitor-Transitionen (mit rekursivem Algorithmus A2).

Theorem 5.6

Die dimensionsbezogenen Semilinearitätsgrenzen für Systeme mit kontrollierenden Zuständen und beliebig vielen Inhibitor-Kanten (ohne Beschränkung auf eine Inhibitor-Stelle) betragen $n^* = 1$ . Es gilt:

$\mathcal{R}_{\mathcal{V},k}(\vec{M}_0) \in \text{sem}(\mathbb{N}^1 \times Q) \quad \text{für alle } \vec{M}_0 \in \text{sem}(\mathbb{N}^1 \times Q).$

Beweis der unteren Schranke: Das Petri-Netz aus Abb. 9 hat eine nicht-semilineare Erreichbarkeitsmenge.

Abb. 9

→ Bild aus dem PDF hier einfügen

Korollar 5.7

Die Erreichbarkeitsmengen der fünfdimensionalen Vektor-Additionssysteme sowie der vierdimensionalen Vektor-Ersetzungssysteme mit mindestens zwei Inhibitor-Vektoren sind bereits unter einelementigen Anfangsmengen im Allgemeinen nicht-semilinear.

Zusammenfassung – Dimensionsbezogene Semilinearitätsgrenzen

Systemklasse	Inhibitor-Kanten / Stellen	Semilinearitätsgrenze $n^*$
VAS / VES mit kontrollierenden Zuständen	keine	2
VAS / VES mit kontrollierenden Zuständen + 1 Inhibitor-Kante	1 Kante	2
VAS / VES mit kontrollierenden Zuständen + beliebig viele Inhibitor-Kanten	beliebig viele Kanten, 1 Stelle	2
VAS / VES mit kontrollierenden Zuständen + beliebig viele Inhibitor-Kanten	beliebig viele Kanten (ohne Einschränkung)	1

Weitere wichtige Erkenntnisse

Kontrollierende Zustände verschieben die Semilinearitätsgrenze deutlich stärker als kontrollierende Stellen.
Erst zwei Inhibitor-Kanten verschieben die Semilinearitätsgrenze gegenüber dem Modell mit kontrollierenden Zuständen.
Die Anzahl der Inhibitor-Stellen ist entscheidender als die reine Anzahl der Inhibitor-Kanten.

Abb. 10 zeigt eine alternative Simulation mit zwei zusätzlichen Stellen und zwei Inhibitor-Kanten.

→ Bild aus dem PDF hier einfügen

Die Ergebnisse dieses Kapitels zeigen, dass nicht-semilineare Erreichbarkeitsmengen vor allem dann entstehen, wenn ausreichend viele Transitionen durch kontrollierende Zustände oder beschränkte Stellen am Feuern gehindert werden können.

„Über Petri-Netze mit inhibitor-Kanten…“ §4

Rainer A. Stawarz29. Juni 2026Allgemein

Kap4

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§4. SEMILINEARE ERREICHBARKEITSMENGEN

Zu den zentralen Motiven dieser Arbeit gehört die Charakterisierung der Petri-Netz-Erreichbarkeitsmengen unter dem Blickwinkel der Semilinearität. Semilineare Erreichbarkeitsmengen sind von verhältnismäßig einfacher Struktur und machen die ansonsten unentscheidbaren Probleme entscheidbar.

Das Konzept der Semilinearität geht im Wesentlichen auf die sogenannte Presburger-Arithmetik zurück [22].

Definition 4.1. (Lineare Menge)

Unter einer linearen Menge zur Basis $b \in \mathbb{N}^n$ mit der Periodenmenge $P = \{p_1, \dots, p_l\} \subseteq \mathbb{N}^n$ verstehen wir die Menge:

$L = L(b, P) = \left\{ x \in \mathbb{N}^n \;\middle|\; \exists \alpha_1, \dots, \alpha_k \in \mathbb{N},\ p_j \in P : x = b + \sum_{j=1}^k \alpha_j p_j \right\}.$

Wir sprechen von einer linearen Menge zu einer Basismenge $B \subseteq \mathbb{N}^n$ mit Periodenmenge $P$ , wenn:

$L = L(B, P) = \bigcup_{b \in B} L(b, P).$

Definition 4.2. (Semilineare Menge)

Jede endliche Vereinigung von linearen Mengen nennen wir eine semilineare Menge. Mit $\text{sem}(\mathbb{N}^n)$ bezeichnen wir das System aller semilinearen Teilmengen von $\mathbb{N}^n$ .

Lemma 4.1.

Sei $l$ ein eindimensionales Teilgitter aus $\mathbb{N}^n$ . Für jede Folge $\{L(x_j, P_j)\}$ mit $L(x_j, P_j) \subseteq l$ und $P_j \subseteq P_{j+1}$ gilt:

$\bigcup_{j=1}^\infty L(x_j, P_j) = \bigcup_{j=1}^k L(x_j, P_j) \quad \text{für ein } k \in \mathbb{N}.$

Lemma 4.2.

Für alle $b \in \mathbb{N}^n$ und alle endlichen Periodenmengen $P \subseteq \mathbb{N}^n$ existiert ein gewöhnliches Vektor-Additionssystem $\mathcal{U}$ mit der Eigenschaft:

$\mathcal{R}_\mathcal{U}(b) = L(b, P).$

Lemma 4.3.

Semilinearität ist (unter geeigneten Voraussetzungen) invariant unter semilinearen Anfangsmengen:

$\forall \mathcal{P} \in \mathcal{C}^n,\ m_0 \in \mathbb{N}^n:\ \mathcal{R}_\mathcal{P}(m_0) \in \text{sem}(\mathbb{N}^n) \implies \forall M_0 \in \text{sem}(\mathbb{N}^n):\ \mathcal{R}_\mathcal{P}(M_0) \in \text{sem}(\mathbb{N}^n).$

Lemma 4.4.

Die Erreichbarkeitsmengen der (mindestens) vierdimensionalen Vektor-Ersetzungssysteme mit genau einer Inhibitor-Kante sind im Allgemeinen **nicht-semilinear** (auch bei einelementigen, semilinearen Anfangsmengen).

Beweis-Skizze (Beispiel Abb. 8): Mit der Startmarkierung $m_0 = (0,0,1,1)$ und den Bedingungen

$\begin{align*} (B1a) &\quad 0 < x_2 + x_3 \le 2^{x_4} \\ (B1b) &\quad x_4 > 0 \\ (B2a) &\quad 0 < 2x_2 + x_3 \le 2^{x_1+1} \\ (B2b) &\quad x_4 = 0 \end{align*}$

zusammen mit $(B12)\ x_4 \le x_1 + 1$ entsteht eine nicht-semilineare Menge. Durch vollständige Induktion wird gezeigt, dass genau die Punkte erreichbar sind, die diese Bedingungen erfüllen.

Abb. 8

→ Hier Bild aus dem PDF einfügen

Korollar 4.5.

Die Erreichbarkeitsmengen der folgenden Gebilde sind unter einelementigen Anfangsmengen im Allgemeinen **nicht-semilinear**:

Gewöhnliche Vektor-Additionssysteme der Dimension $n \ge 6$
Gewöhnliche Vektor-Ersetzungssysteme der Dimension $n \ge 5$
Gewöhnliche Vektor-Additionssysteme und Vektor-Ersetzungssysteme mit kontrollierenden Zuständen der Dimension $n \ge 3$
Vektor-Ersetzungssysteme mit genau einem Inhibitor-Vektor der Dimension $n \ge 4$

Lemma 4.6.

Sei $\mathcal{V}$ ein gewöhnliches Petri-Netz mit $(PN^*)$ der Dimension $n$ . Für alle Komponentenpaare $j \ne k$ existiert eine effektiv berechenbare Konstante $g^{j,k} \in \mathbb{N}^n$ mit $g_j^{j,k} = g_k^{j,k} = 0$ , sodass die Erreichbarkeitsmengen von $\mathcal{V}$ **strikt innerhalb** von $G^{j,k} = \{x \in \mathbb{N}^n \mid x \ge g^{j,k}\}$ durch semilineare Teilmengen eingehüllt werden können.

Zusammenfassung der Erkenntnisse

Nicht-semilineare Erreichbarkeitsmengen treten bereits bei relativ kleinen Dimensionen auf. Andererseits „neigen“ viele Petri-Netze (insbesondere mit $(PN^*)$ ) in „hohen“ Regionen stark zur Semilinearität. Lemma 4.6 macht diese Beobachtung präzise.

Die Simulation kontrollierender Zustände (siehe §3) sowie die Ergebnisse dieses Kapitels legen nahe, dass nicht-semilineare Mengen vor allem dann entstehen, wenn genügend viele Transitionen durch kontrollierende Zustände oder beschränkte Stellen am Feuern gehindert werden können.

Kap4

„Über Petri-Netze mit inhibitor-Kanten…“ §3

Rainer A. Stawarz29. Juni 2026Allgemein

Kap3

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§3. SIMULATION VON VARIANTEN DES GRUNDMODELLS

Eine weitere Variante der (nicht notwendigerweise gewöhnlichen) Petri-Netze wird unsere Betrachtungen in diesem Paragraphen wesentlich erleichtern. Es handelt sich um Petri-Netze mit kontrollierenden Zuständen.¹

Definition 3.1.

Ein Petri-Netz mit (endlich vielen) kontrollierenden Zuständen ist ein Tupel 𝒫^1,0 = (S, T, Q, κ) mit folgenden Komponenten und Eigenschaften:

(QN1) $S = \{s_1, \dots, s_n\}$ ist eine endliche Menge von Stellen;
(QN2) $T = \{t_1, \dots, t_l\}$ ist eine endliche Menge von Transitionen;
(QN3) $Q = \{q_1, \dots, q_p\}$ ist eine endliche Menge von kontrollierenden Zuständen;
(QN4) $S \cap T = S \cap Q = T \cap Q = \emptyset$ ;
(QN5) $\kappa : (S \times T) \cup (T \times S) \to \mathbb{N} \cup \{\iota\}$ ist die erweiterte Kantenabbildung;
(QN6) $q^a : T \to Q$ und $q^e : T \to Q$ sind zwei Zustandsabbildungen, die allen Transitionen einen Anfangs- und Endzustand zuordnen.

Gilt $\kappa^{-1}(\{\iota\}) = \emptyset$ , dann sprechen wir von einem gewöhnlichen Petri-Netz mit kontrollierenden Zuständen. Die Markierung beinhaltet neben der üblichen Stellenmarkierung stets den augenblicklich vorliegenden kontrollierenden Zustand. Wir sprechen von einer Multimarkierung:

$m = (m(s), m(q)) : S \cup \{q\} \to \mathbb{N} \cup Q$

mit $m(q) \in Q$ und $m(s) \in \mathbb{N}$ für alle $s \in S$ .

Eine Transition $t \in T$ ist nur dann aktiviert, wenn ihr Anfangszustand $q^a(t)$ mit dem kontrollierenden Zustand $m(q)$ übereinstimmt:

$\forall s \in S : [m(s) - \kappa(s, t) \ge 0] \land [(\kappa(s, t) = \iota) \to (m(s) = 0)] \land [m(q) = q^a(t)].$

Schaltregel für Petri-Netze mit kontrollierenden Zuständen

Feuert eine aktivierte Transition $t$ im Zustand $m$ und ist der Zustand nach dem Schaltvorgang $m'$ (formal: $m \to^1 m'$ ), dann gilt:

$m'(s) = m(s) + \kappa(t, s) - \kappa(s, t) \quad \text{für alle } s \in S,$
$m'(q) = q^e(t).$

¹ Kontrollierende Zustände wurden in [10] im Zusammenhang mit gewöhnlichen Vektor-Additionssystemen eingeführt. Unsere Definition verallgemeinert dieses Konzept ein wenig.

Beispiel: Abbildung 5

Die Abb. 5 zeigt ein gewöhnliches Petri-Netz mit zwei kontrollierenden Zuständen $q_1, q_2$ (der augenblicklich vorliegende kontrollierende Zustand ist durch die doppelt eingekreiste Stelle $q$ markiert) und drei Stellen. Die Transition $t_2$ ist eine reine Zustandsüberführungstransition.

Abb. 5

→ Hier Bild aus dem PDF einfügen

Die Schaltfolge $t_1 t_2 t_3 t_4 (t_1)^2 t_2 t_3$ erzeugt denselben projizierten Schaltpfad wie in den vorherigen Beispielen.

Definition 3.2. (Projektion)

Unter einer Projektion der Erreichbarkeitsmenge $\mathcal{R}_\mathcal{P}(\vec{M}_0)$ eines Petri-Netzes $\mathcal{P}^{1,0}$ auf ein Gitter $G = \mathbb{N}^m \times Q^k$ (mit $m \le n$ und $k \in \{0,1\}$ ) verstehen wir die Menge:

$\mathcal{R}_\mathcal{P}(\vec{M}_0) \downarrow_{\{x_1,\dots,x_m,q\}} = \{\vec{x} \in G \mid \exists \vec{x}' \in \mathcal{R}_\mathcal{P}(\vec{M}_0) : (x'_1,\dots,x'_m,q) = (x_1,\dots,x_m,q)\}$

oder analog ohne den Zustand $q$ .

Lemma 3.1.

Jedes Petri-Netz $\mathcal{P}^{1,0}$ kann simuliert werden durch ein gleichdimensionales Petri-Netz $\mathcal{R}^{1,0}$ mit zusätzlichen kontrollierenden Zuständen, sodass $(PN^*)$ erfüllt ist. Es gilt:

$\mathcal{R}_\mathcal{P}(\vec{M}_0)|_{q = q_j} = \mathcal{R}_\mathcal{R}(\vec{M}_0)|_{q = q_j} \quad \text{für alle } q_j \in Q_*.$

Lemma 3.2.

Jedes Petri-Netz $\mathcal{P}^{1,0}$ mit kontrollierenden Zuständen kann simuliert werden durch ein Petri-Netz $\mathcal{R}$ (ohne kontrollierende Zustände) mit Hilfe von zwei zusätzlichen Stellen $s_1^{(z)}, s_2^{(z)}$ , wobei diese kontrollierend sind für alle $t \in T$ .

$\mathcal{R}_\mathcal{P}(\vec{M}_0) \downarrow_{\{s_1,\dots,s_n\}} = \mathcal{R}_\mathcal{R}(M_0) \downarrow_{\{s_1,\dots,s_n\}}$

Lemma 3.3.

Jedes Petri-Netz $\mathcal{P}^{1,0}$ mit kontrollierenden Zuständen kann simuliert werden durch ein Petri-Netz $\mathcal{R}$ (ohne kontrollierende Zustände) mit Hilfe von drei zusätzlichen Stellen $s_1^{(z)}, s_2^{(z)}, s_3^{(z)}$ , sodass $(PN^*)$ erfüllt ist.

Korollar 3.4. & 3.5.

Jedes Petri-Netz $\mathcal{P}^1$ (bzw. $\mathcal{P}^{1,0}$ ) kann durch ein Petri-Netz $\mathcal{R}^1$ mit drei zusätzlichen Stellen simuliert werden, sodass $(PN^*)$ erfüllt ist.

Korollar 3.6.

Das allgemeine Erreichbarkeitsproblem ist für gewöhnliche Petri-Netze mit kontrollierenden Zuständen unabhängig von $(PN^*)$ entscheidbar.

Korollar 3.7.

Sei $S^{(e)} \subseteq S$ mit $\mathcal{R}_e(\cdot) \downarrow_{s} \subseteq \{0,\dots,c\}$ für ein $c \in \mathbb{N}$ und alle $s \in S^{(e)}$ . Dann kann $\mathcal{P}^{1,0}$ im Sinne der Projektion auf $S \setminus S^{(e)}$ durch ein Petri-Netz der Dimension $n = |S \setminus S^{(e)}| + 2$ (bzw. +3 bei $(PN^*)$ ) simuliert werden.

Abbildungen

Abb. 6 und Abb. 7 zeigen Beispiele für die Simulation kontrollierender Zustände (mit und ohne Inhibitor-Kante).

→ Hier die entsprechenden Bilder aus dem PDF einfügen

Aus unseren Überlegungen folgt, dass kontrollierende Zustände sowie kontrollierende Stellen nichts an dimensionsunabhängigen Aussagen über Petri-Netze ändern. Insbesondere gilt Korollar 3.6.

„Über Petri-Netze mit inhibitor-Kanten…“ §2

Rainer A. Stawarz29. Juni 2026Allgemein

Kap2

💡 Nachfolgender Beitrag wurde mittels OCR/KI (xAI) erstellt und weicht vom obigen Original erheblich ab 💡	Ø

§2. GRUNDLEGENDE KONZEPTE

Die Diskussion der grundlegenden Konzepte lehnen wir zunächst an gewöhnliche Petri-Netze an.

Definition 2.1

Ein gewöhnliches Petri-Netz ist ein Tupel $\mathcal{P} = (S, T, \kappa)$ mit folgenden Komponenten und Eigenschaften:

(PN1) $S = \{s_1, \dots, s_n\}$ ist eine endliche Menge von Stellen;
(PN2) $T = \{t_1, \dots, t_l\}$ ist eine endliche Menge von Transitionen;
(PN3) $S \cap T = \emptyset$ ;
(PN4) $\kappa: (S \times T) \cup (T \times S) \to \mathbb{N}$ ist eine Kantenabbildung.

Das Abbild eines solchen Tupels ist ein gerichteter Graph, mit Stellen und Transitionen als Knoten, sowie beschrifteten Kanten von Stellen zu Transitionen und vice versa. Die Kantenbeschriftung symbolisiert die sogenannte Kantenvielfachheit, die die Abbildung aus (PN4) beinhaltet. Kanten mit $\kappa(\cdot, \cdot) = 0$ sind als nicht existent anzusehen.

Eine Transition $t$ kann Ein- und Ausgangsstellen haben (es gilt entsprechend $\kappa(s, t) > 0$ , bzw. $\kappa(t, s) > 0$ ). Stellen, die gleichzeitig Ein- und Ausgangsstellen für eine Transition sind, nennen wir kontrollierende Stellen. Es kann zusätzlich gefordert werden, dass das Petri-Netz solche Stellen nicht enthält. Es gilt dann:

$(\text{PN}^*) \quad \forall s \in S, \, t \in T: \quad \kappa(s, t) = 0 \lor \kappa(t, s) = 0.$

Ein Petri-Netz ist demnach ein rein statisches Gebilde. Dynamische Eigenschaften werden ihm erst durch die sogenannte Markierung verliehen (wir sprechen vom markierten Petri-Netz):

(PN5) $m: S \to \mathbb{N}$ .

Diese Markierung fixiert einen Zustand des gegebenen Petri-Netzes und kann nach bestimmten Regeln, sogenannten Schaltregeln, verändert werden. Der Zustandsüberführungsvorgang bleibt nur den sogenannten aktivierten Transitionen vorbehalten.

Eine Transition $t \in T$ ist aktiviert (auch schaltbar), wenn gilt:

$\forall s \in S: \quad m(s) - \kappa(s, t) \ge 0.$

Schaltregel für gewöhnliche Petri-Netze

Feuert eine aktivierte Transition $t$ im Zustand $m$ und ist der Zustand nach dem Schaltvorgang $\tilde{m}$ (formal: $m \to^1 \tilde{m}$ ), dann gilt:

$\tilde{m}(s) = m(s) + \kappa(t, s) - \kappa(s, t) \quad \text{für alle } s \in S.$

Beispiel

Die Abb. 1 zeigt ein Petri-Netz, bestehend aus drei Stellen $s_1, s_2, s_3$ (dargestellt durch Ringe) und einer Transition $t$ (dargestellt durch einen Balken), mit folgender Kantenabbildung:

$\kappa(k_1, k_2) = \begin{cases} 3 & \text{falls } k_1 = s_2 \land k_2 = t, \\ 2 & \text{falls } k_1 = s_1 \land k_2 = t, \\ 1 & \text{falls } k_1 = t \land k_2 = s_3, \\ 0 & \text{sonst.} \end{cases}$

Abb. 1

→ Hier Bild aus dem PDF einfügen

Keine dieser Stellen ist kontrollierend – (PN*) ist damit erfüllt.

Den Zustand (Markierung) des Petri-Netzes pflegen wir durch direktes Einzeichnen der Marken in die Stellen. Der Anfangszustand (Abb. 1 links) ist demnach $m = (3,3,1)$ , der Endzustand (Abb. 1 rechts) $m = (1,0,2)$ . Bildhaft gesprochen wandern die Marken von den Eingangsstellen hinüber auf die Ausgangsstellen unter Berücksichtigung der Kantenvielfachheiten.

Im Allgemeinen werden aber offensichtlich auch weitere Schaltvorgänge möglich sein – insbesondere durch andere Transitionen. Derartige Schaltfolgen sind vor allem im Hinblick auf das bereits angesprochene Erreichbarkeitsproblem von besonderem Interesse für uns.

Sei $T^*$ die Menge aller Wörter über dem (endlichen) Alphabet $T$ , zusammen mit dem leeren Wort $\lambda$ ( $T^*$ ist damit ein Monoid hinsichtlich der Konkatenation). Unter einer Transitionenfolge verstehen wir jedes Element $\tau \in T^*$ .

Sei $\tau = (t_{j(1)}, \dots, t_{j(k)}) \in T^*$ mit $j(i) \in \{1, \dots, l\}$ , $1 \le i \le k$ . Wir sprechen von einer zulässigen Transitionenfolge (auch Schaltfolge) zu gegebenem Zustand $m$ , wenn gilt:

$\forall s \in S, \, i \in \{1, \dots, k\}: \left[ m(s) + \left( \sum_{v=1}^{i-1} [\kappa(t_{j(v)}, s) - \kappa(s, t_{j(v)})] \right) - \kappa(s, t_{j(i)}) \right] \ge 0.$

Da jede Schaltfolge eine Art zusammengesetzter Transition ist, können wir die erweiterte Schaltregel für gewöhnliche Petri-Netze folgendermaßen angeben:

$m \to^* \tilde{m} \quad \implies \quad \tilde{m}(s) = m(s) + \sum_{v=1}^{k} [\kappa(t_{j(v)}, s) - \kappa(s, t_{j(v)})] \quad \text{für alle } s \in S.$

Beispiel: Abbildung 2

Abb. 2 schildert die Zustandsveränderung eines Petri-Netzes beim Feuern der (zulässigen) Schaltfolge $t_1 t_2 t_3 t_4 (t_1)^2 t_2 t_3$ mit einigen Zwischenzuständen. Im Gegensatz zum vorherigen Beispiel enthält dieses Petri-Netz zwei kontrollierende Stellen: $s_4$ (kontrollierend für $t_1$ ) und $s_5$ (kontrollierend für $t_3$ ). Es gilt nämlich:

$\begin{align*} \kappa(s_4, t_1) &= \kappa(t_1, s_4) = 1 \\ \kappa(s_5, t_3) &= \kappa(t_3, s_5) = 1 \end{align*}$

Abb. 2

→ Hier Bild aus dem PDF einfügen

Diese beiden Stellen weisen darüber hinaus noch eine andere interessante Eigenschaft auf: es gilt stets $m(s_4) = 1 - m(s_5)$ . Zwei Stellen $s$ und $\bar{s}$ nennen wir zueinander komplementär, wenn es eine Konstante $a = a(m_0) \in \mathbb{N}_+$ gibt, mit:

$m(\bar{s}) = a - m(s) \quad \text{für alle } m \in \mathcal{R}_\mathcal{P}(m_0).$

Definition 2.2.

Die Erreichbarkeitsmenge eines Petri-Netzes $\mathcal{P} = (S, T, \kappa)$ mit dem Anfangszustand $m_0$ ist die Menge:

$\mathcal{R}_\mathcal{P}(m_0) = \{ m \mid m_0 \to^* m \text{ für eine zulässige Schaltfolge } \tau \in T^* \}.$

Die Erreichbarkeitsmenge kann sich auch auf eine (nicht notwendigerweise endliche) Menge $M_0$ von Anfangszuständen beziehen:

$\mathcal{R}_\mathcal{P}(M_0) = \{ m \mid \exists m_0 \in M_0: m_0 \to^* m \text{ für eine zulässige Schaltfolge } \tau \in T^* \}.$

Gilt $m \in \mathcal{R}_\mathcal{P}(m_0)$ , so sagen wir, dass die Markierung $m$ von $m_0$ aus erreichbar ist. Das allgemeine Erreichbarkeitsproblem ist gleichbedeutend mit der Aufgabe zu entscheiden, ob im gegebenen Petri-Netz ein Zustand $m$ von einem Anfangszustand $m_0$ aus erreichbar ist.

Das Inklusions- bzw. Gleichheitsproblem ist die Prüfung folgender Relationen für zwei Petri-Netze $\mathcal{P}$ und $\mathcal{Q}$ :

$\mathcal{R}_\mathcal{P}(m_0) \subseteq \mathcal{R}_\mathcal{Q}(m_0)$ für das Inklusionsproblem
$\mathcal{R}_\mathcal{P}(m_0) = \mathcal{R}_\mathcal{Q}(m_0)$ für das Gleichheitsproblem

Eine solche Prüfung ist allerdings nur dann sinnvoll, wenn $\mathcal{P}$ und $\mathcal{Q}$ von gleicher Dimension sind, d. h. $|S_\mathcal{P}| = |S_\mathcal{Q}|$ .

Petri-Netze können einerseits sehr anschaulich durch PN-Graphen dargestellt werden – besitzen aber andererseits äquivalente Strukturen von rein algebraischem Charakter, sogenannte Vektor-Additionssysteme und Vektor-Ersetzungssysteme.

Definition 2.3.

Ein Vektor-Ersetzungssystem $\mathcal{V}$ zum Anfangsvektor $m_0 \in \mathbb{N}^n$ ist die Menge:

$\mathcal{V} = \{ v_j = (t'_j, t''_j) \in \mathbb{N}^n \times \mathbb{Z}^n \mid 1 \le j \le l,\ t'_j + t''_j \ge 0 \}.$

Die Vektorpaare bestehen jeweils aus dem Testvektor $t'_j$ und dem Ersetzungsvektor $t''_j$ . Die Ersetzungsregel lautet:

$\tilde{m} = m + t''_j.$

Die völlige Gleichwertigkeit der Vektor-Ersetzungssysteme und Petri-Netze ist offensichtlich.

Ein Vektor $v = (t', t'')$ genügt der Relation (VAS) genau dann, wenn die äquivalente Transition $t$ von keiner Stelle kontrolliert wird. Es besteht die Äquivalenz:

$[v_j \text{ erfüllt (VAS) für alle } j] \iff (\text{PN}^*).$

Definition 2.4.

Ein Vektor-Additionssystem $\mathcal{U}$ zum Anfangsvektor $m_0 \in \mathbb{N}^n$ ist die Menge:

$\mathcal{U} = \{ v_j \in \mathbb{Z}^n \mid 1 \le j \le l \}.$

Jeder Vektor aus $\mathcal{U}$ ist gleichzeitig Test- und Ersetzungsvektor. Eine Ersetzung $v_j$ ist zulässig, wenn $m + v_j \ge 0$ ist. Die Ersetzungsregel lautet: $\hat{m} = m + v_j$ .

Das Vorhandensein einer Mindestzahl von Marken auf bestimmten Stellen als Voraussetzung für eventuelles Feuern von Transitionen ist eine Eigenschaft der gewöhnlichen Petri-Netze, die im Allgemeinen nicht invertierbar ist. Eine solche Abhängigkeit ist aber in manchen Fällen unentbehrlich – vor allem im Hinblick auf die WPNC-Berechenbarkeit von Funktionen, die das „Testen auf 0“ notwendig machen.

Definition 2.5.

Ein Petri-Netz mit Inhibitor-Kanten $\mathcal{P}^i = (S, T, \kappa)$ ist ein Tupel mit den Komponenten (PN1), (PN2), (PN3), (PN5) und mit einer erweiterten Kantenabbildung:

$(\text{IN4}) \quad \kappa: (S \times T) \cup (T \times S) \to \mathbb{N} \cup \{\iota\}$

mit $\kappa^{-1}(\{\iota\}) \subseteq (S \times T)$ .

Wir definieren die additiven Verknüpfungen von $\iota$ mit allen anderen Elementen wie folgt:

$\alpha + \iota = \alpha - \iota = \alpha \quad \forall \alpha \in \mathbb{N} \cup \{\iota\}.$

Die Schaltregel ist mit der für gewöhnliche Petri-Netze scheinbar identisch. Etwas anderes verbirgt sich jedoch hinter dem Begriff „aktivierte Transition“. Diese Bezeichnung trifft auf eine Transition $t \in T$ zu, wenn gilt:

$\forall s \in S: [m(s) - \kappa(s, t) \ge 0] \land [(\kappa(s, t) = \iota) \implies (m(s) = 0)].$

Graphisch gesehen sind Überlappungen beider Kantenarten möglich, was aber unsere Definition ausschließt. Möglich dagegen ist eine andere Konstellation. Hier gilt $\kappa(t, s) > 0 \land \kappa(s, t) = \iota$ für die Stelle $s$ und Transition $t$ . Wir sprechen von einer selbstblockierenden (auch rückgekoppelten) Inhibitor-Transition.

Abb. 3

→ Hier Bild aus dem PDF einfügen

Einer Präzisierung bedarf noch der Begriff „kontrollierende Stellen“. Unter einer kontrollierenden Stelle im Petri-Netz mit Inhibitor-Kanten verstehen wir ein $s \in S$ mit $\kappa(t, s) > 0 \land [\kappa(s, t) > 0 \lor \kappa(s, t) = \iota]$ für eine Transition $t \in T$ .

Definition 2.6.

Ein Vektor-Ersetzungssystem mit Inhibitor-Vektoren zum Anfangsvektor $m_0 \in \mathbb{N}^n$ ist die Menge:

$\mathcal{V} = \{ v_j = (t_j^t, t_j^s) \in (\mathbb{N} \cup \{\iota\})^n \times \mathbb{Z}^n \mid 1 \le j \le l,\ t_j^t + t_j^s \ge 0 \}.$

Es muss gefordert werden:

$(\text{IV}) \quad \forall v \in \mathcal{V}, \, j \in \{1,\dots,n\}: (t_j^t = \iota) \implies (t_j^s = 0).$

Definition 2.7.

Ein Vektor-Additionssystem mit Inhibitor-Vektoren zum Anfangsvektor $m_0 \in \mathbb{N}^n$ ist die Menge:

$\mathcal{U} = \{ v_j \in (\mathbb{Z} \cup \{\iota\})^n \mid 1 \le j \le l \}.$

In der vorliegenden Arbeit blicken wir nur sporadisch auf Petri-Netze mit mehreren Inhibitor-Kanten. Da bereits zwei Inhibitor-Kanten die Simulation von Turing-Maschinen ermöglichen, können weitere solche Kanten die Leistungsfähigkeit der Petri-Netze ohnehin nicht mehr entscheidend steigern. Außerdem ist das Erreichbarkeitsproblem in diesem Fall als unentscheidbar bekannt. Unsere Aufmerksamkeit gilt daher primär den Petri-Netzen mit genau einer Inhibitor-Kante, die das bislang offene Erreichbarkeitsproblem aufwerfen.

Beispiel: Abbildung 4

Zum Schluss dieses Kapitels geben wir ein Beispiel für ein Petri-Netz mit einer Inhibitor-Kante (vgl. Abb. 4), wobei die Parallelitäten zum vorangegangenen Beispiel unübersehbar sein dürften. Wir sagen, dass beide Petri-Netze einander simulieren. Zwar stimmen deren Dimensionen nicht überein. Betrachten wir aber erneut die (zulässige) Schaltfolge $t_1 t_2 t_3 t_4 (t_1)^2 t_2 t_3$ , so stellen wir fest, dass die durch diese Schaltfolge erzeugten Schaltpfade identisch sind, bezüglich $s_1, s_2, s_3$ .

Abb. 4

→ Hier Bild aus dem PDF einfügen

Die erweiterte Kantenabbildung ist dem Graphen zu entnehmen. Stattdessen wollen wir das zu unserem Petri-Netz äquivalente Vektor-Ersetzungssystem (mit genau einem Inhibitor-Vektor) vollständig angeben.

Die bereits vorgestellten Konzepte, wie z. B. Erreichbarkeitsmengen und die darauf zurückgehenden Schlüsselprobleme, sind identisch zu formulieren. Zu beachten ist nur, dass etwas anderes unter aktivierten Transitionen bzw. zulässigen Transitionenfolgen zu verstehen ist.

Im vorangegangenen Kapitel haben wir bereits angedeutet, dass Inhibitor-Kanten diese Probleme erheblich erschweren können. Die Tatsache, dass zwei und mehr solche Kanten das Erreichbarkeitsproblem unentscheidbar machen, ist ein Indiz dafür, dass die Inhibitor-Kanten eine echte, qualitative Verallgemeinerung der gewöhnlichen Petri-Netze darstellen.