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

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.