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

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.