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

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.