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

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