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

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