Next: 6. Analyse Up: 5. Reduktion Previous: 5.2 Hilfsfunktionen

5.3 Reduktionsprozeduren

`<F>` Fusion of congruent nodes

INA sucht nach jeweils zwei Plätzen oder zwei Transitionen, die mit allen übrigen Knoten des Netzes in der gleichen Weise verbunden sind, sogenannte parallele Knoten [Sta90, Definition 9.3 (87)].

Abbildung 5.2: Ein Netz mit zwei parallelen Plätzen und Transitionen (reduce_f.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_f.eps}}\end{figure}$

Abbildung 5.2 zeigt ein Netz mit zwei parallelen Plätzen (p1 und p2) und zwei parallelen Transitionen (t1 und t2).
Sie müssen die zu untersuchende Knotenart direkt angeben: Check places (P), transitions (T) or exit (E) ? Nach der Eingabe von <P> bzw. <T> für die Suche nach Plätzen bzw. Transitionen meldet INA entweder, daß keine parallelen Knoten gefunden (No application possible!) oder wieviele Knoten gelöscht wurden (nodes deleted). Normalerweise werden immer die Knoten mit der höheren Nummer gelöscht. Bei parallelen Plätzen wird dagegen der Platz mit der kleineren Nummer gestrichen, falls er mehr Marken trägt [Sta90, Regel 3 (88)].

Abbildung 5.3: Reduktionen bezüglich paralleler Knoten des Beispielnetzes 5.2
$\begin{figure}\fbox{\epsfbox{reduc_f.eps}}\end{figure}$

Das Netz des Beispiels 5.2 wird durch Eingabe von <P> zum linken Netz des Beispiels 5.3. Da der Platz p₂ eine größere Nummer als p₁ hat und p₁ nicht mehr Marken als p₂ enthält, wird der Platz p₂ gelöscht. Wird weiter mit <T> reduziert, so ergibt sich das rechte Netz des Beispiels 5.3. Die Transition t₂ wird gelöscht, da sie eine größere Nummer als die Transition t₁ hat.
Im Session-Report finden Sie folgendes Protokoll:
Fuse:
p2 deleted
 1 place(s) deleted 
t2 deleted
 1 transition(s) deleted

`<M>` Merging of equivalent places

Dieses Kommando verschmilzt äquivalente Plätze des Netzes. Zwei Plätze p₁ und p₂ sind äquivalent, wenn

beide Plätze je genau eine Nachtransition t₁ bzw. t₂ besitzen,
die Vielfachheit der Bögen von p₁ zu t₁ bzw. von p₂ zu t₂ gleich 1 ist und
die Transitionen t₁ bzw. t₂ mit allen von p₁ und p₂ verschiedenen Plätzen auf die gleiche Weise verbunden sind [Sta90, Definition 9.4 (88)].

Abbildung 5.4: Ein Netz mit äquivalenten Plätzen und deren Reduktion (reduce_m.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_m.eps}}\end{figure}$

Im Netz des Beispiels 5.4 sind die Plätze p₁ und p₂ äquivalent.
Falls INA zwei äquivalente Plätze p₁ und p₂ findet, so werden der Platz p₂ (mit einer höheren Nummer als p₁) sowie seine Nachtransition t₂ gestrichen, die auf p₂ befindlichen Marken zusätzlich auf p₁ gelegt und die nach p₂ führenden Bögen nach p₁ geführt [Sta90, Regel 4 (89)].
Das rechte Netz des Beispiels 5.4 zeigt die Reduktion des linken Netzes. Der Platz p₂ und seine Nachtransition t₂ werden gelöscht, die Marke von p₂ wird auf p₁ gelegt und der Bogen von t₄ zu p₂wird nach p₁ geführt.
Im Session-Report finden Sie folgendes Protokoll:
Merge equivalent places:
Transition  2 deleted, Place 2 deleted

`<A>` ELIMINATION of F(pF)=p -places

Dieses Kommando verschmilzt Vor- mit Nachtransitionen. Hierbei bezeichnet pF alle Nachtransitionen des Platzes p und F(pF) alle Vorplätze der Nachtransitionen von p. sind die Plätze p, die die einzigen Vorplätze ihrer Nachtransitionen sind.
Gesucht wird ein Platz mit folgenden Eigenschaften [Sta90, Vorauss. Regel 5 (90)]:

p hat k>0 Vortransitionen $t_1,\ldots,t_k$
p hat n>0 Nachtransitionen $t_1',\ldots,t_n'$
keine Transition ist zugleich Vor- und Nachtransition von p
wenigstens eine Nachtransition von p hat einen Nachplatz
p ist der einzige Vorplatz seiner Nachtransitionen
alle bei p entspringende Bögen haben die gleiche Vielfachheit v

falls p genau eine Nachtransition hat (n=1), dann haben alle bei p einmündenden Bögen eine durch v teilbare Vielfachheit
falls p dagegen mehr als eine Nachtransition hat (n>1), dann haben alle bei p einmündenden Bögen die Vielfachheit v

Abbildung 5.5: Ein mit <A> reduzierbares Netz und das Ergebnis (reduce_a.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_a.eps}}\end{figure}$

Der Platz p₁ des linken Netzes des Beispiels 5.5 erfüllt die obigen Bedingungen.
Falls INA einen Platz findet, der allen Bedingungen genügt, so werden eventuell auf p liegende Marken weggeschaltet, bis weniger als v Marken auf p sind. Dann werden die Vortransitionen $t_1,\ldots,t_k$ , der Platz p selbst und die Nachtransitionen $t_1',\ldots,t_n'$ gestrichen, dafür werden $k\cdot n$ neue Transitionen t_i,j so eingeführt, daß ein Schalten von t_i,j die gleiche Wirkung wie ein Schalten von t_igefolgt von x-maligem Schalten von t_j', wobei x die Vielfachheit des Bogens von t_i nach p dividiert durch v ist [Sta90, Regel 5 (90)]. INA meldet nur die Anzahl der gelöschten Plätze.
Im Beispiel 5.5 ergibt sich das rechte Netz. Der Platz p₁und die Transitionen t₁, t₂ und t₄ werden gelöscht und durch die Transitionen t₅ und t₆ ersetzt. Das Schalten von t₅im reduzierten Netz hat die gleiche Wirkung wie das Schalten von t₄ und t₁ im alten Netz, genauso verhält es sich mit dem Schalten von t₆ und dem Schalten von t₄ und t₂.
Im Session-Report finden Sie folgendes Protokoll:
place elimination A:
New transition 5 replaces transitions 4 * 1
New transition 6 replaces transitions 4 * 2
Place 1 deleted

`<B>` ELIMINATION of (Fp)F=p -places

Dieses Kommando verschmilzt eine Vor- mit Nachtransitionen. Hierbei bezeichnet Fp alle Vortransitionen des Platzes p und (Fp)F alle Nachplätze der Vortransitionen von p. sind die Plätze p, die die einzigen Nachplätze ihrer Vortransitionen sind.
Gesucht wird ein Platz mit folgenden Eigenschaften [Sta90, Vorauss. Regel 6 (92)]:

p hat genau eine Vortransitionen t₀ und p ist der einzige Nachplatz dieser Transition.
p hat n>0 Nachtransitionen $t_1',\ldots,t_n'$
keine Transition ist zugleich Vor- und Nachtransition von p
t₀ ist die einzige Nachtransition ihrer Vorplätze
alle bei p einmündenden oder entspringenden Bögen haben die gleiche Vielfachheit v und auf p liegen weniger als v Marken

Abbildung 5.6: Ein mit <B> reduzierbares Netz und das Ergebnis (reduce_b.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_b.eps}}\end{figure}$

Der Platz p₃ des linken Netzes des Beispiels 5.6 erfüllt die obigen Bedingungen.
Falls INA einen Platz findet, der allen Bedingungen genügt, so werden die Vortransition t₀, der Platz p selbst und die Nachtransitionen $t_1',\ldots,t_n'$ gestrichen, dafür werden n neue Transitionen $t_1,\ldots,t_n$ so eingeführt, daß ein Schalten von t_j die gleiche Wirkung wie ein Schalten von t₀ gefolgt von einem Schalten von t_j' [Sta90, Regel 6 (92)]. INA meldet nur die Anzahl der gelöschten Plätze.
Im Beispiel 5.6 ergibt sich das rechte Netz. Der Platz p₃und die Transitionen t₀, t₁ und t₂ werden gelöscht und durch zwei Transitionen t₅ und t₆ ersetzt. Das Schalten von t₅im reduzierten Netz hat die gleiche Wirkung wie das Schalten von t₀ und t₁ im alten Netz, genauso verhält es sich mit dem Schalten von t₆ und dem Schalten von t₀ und t₂.
Im Session-Report finden Sie folgendes Protokoll:
place elimination B:
Transition 5 replaces transitions 1 * 0
Transition 6 replaces transitions 2 * 0
Place 3 deleted

`<C>` ELIMINATION of looping places

Dieses Kommando sucht nach beschränkten und unbeschränkten Plätzen, die folgende Bedingung erfüllen: [Sta90, Vorauss. Regel 7 (95) mit Ergänzungen]

jede Transition t zieht höchstens so viele Marken von p ab, wie sie auf p aufbringt
p ist ausreichend markiert
Der Platz p wird gestrichen, falls dadurch keine isolierte Transitionen entstehen. INA meldet die Anzahl der gelöschten Plätze.

Abbildung 5.7: Ein Netz mit einem zu reduzierenden Laufplatz (reduce_c.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_c.eps}}\end{figure}$

Im Netz des Beispiels 5.7 erfüllt der Platz p₁die Bedingung und wird deshalb gelöscht.
Zu Beginn der Reduktion mit diesem Kommando stellt INA die Frage Shall we delete only bounded places? Falls Sie mit <Y> antworten, werden nur beschränkte Plätze gelöscht, sonst auch unbeschränkte. Ein Platz p ist unbeschränkt, wenn ein Schalten einer Transition t mehr Marken auf p bringt, als sie von p abzieht und die Transition t lebendig ist, d.h. p ausreichend markiert ist.
Falls im Netz des Beispiels 5.7 die Vielfachheit des Bogens von t₁ nach p₁ um eins auf zwei erhöht wird, dann ist der Platz p₁ unbeschränkt und wird deshalb nur gelöscht, wenn Sie die Abfrage mit <N> beantworten. Im Session-Report finden Sie folgendes Protokoll:
place elimination C:
only bounded places to be deleted
place elimination C:
bounded and unbounded places to be deleted
p1 deleted, was unbounded, if the net is live.

`<U>` DELETION of looping transitions

Dieses Kommando löscht alle Transitionen t, die folgende Bedingungen erfüllt [Sta90, Regel 8 (95)]:

das Schalten von t ändert die Markierung nicht
es existiert eine Transition t', die zu ihrer Konzessionierung auf jedem Vorplatz von t mindestens so viele Marken wie t anfordert
Diese Situation wird als Schleife bezeichnet. Falls INA eine solche Transition findet, wird diese gelöscht. INA meldet die Anzahl der gelöschten Transitionen.

Abbildung 5.8: Ein Netz mit einer zu reduzierenden Schleife (reduce_u.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_u.eps}}\end{figure}$

Ein einfaches Beispiel für eine Schleife zeigt das Netz 5.8. Das Schalten der Transition t₁ ändert die Markierung des Netzes nicht. Da die Transition t₂ mindestens so viele Marken von p₁ abzieht wie t₁, wird t₁ gelöscht.
Im Session-Report finden Sie das folgende Protokoll:
transition elimination U:
transition 1 deleted

`<V>` DELETION of single output transitions

Dieses Kommando verschmilzt einen Vor- mit den Nachplätzen. Gesucht wird eine Transitionen mit folgenden Eigenschaften [Sta90, Vorauss. Regel 9 (95)]:

t hat genau einen Vorplatz p
die Vielfachheit des Bogens von p nach t ist eins
p hat k>0 Vortransitionen $t_1,\ldots,t_k$
p ist kein Nachplatz von t, aber t hat Nachplätze

Abbildung 5.9: Ein mit <V> reduzierbares Netz (reduce_v.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_v.eps}}\end{figure}$

Die Transition t₀ des Netzes des Beispiels 5.9 erfüllt die obigen Bedingungen.
Falls INA eine Transition findet, die allen Bedingungen genügt, so wird t solange geschaltet, bis p keine Marke mehr trägt. Dann wird die Transition t, der Platz p und die Vortransitionen $t_1,\ldots,t_k$ gestrichen, dafür werden k neue Transitionen $t_j^\star$ so eingeführt, daß ein Schalten von $t_j^\star$ die gleiche Wirkung wie ein Schalten von t_j gefolgt von x-maligem Schalten von $t_j^\star$ , wobei x die Vielfachheit des Bogens von t_j nach p ist [Sta90, Regel 9 (95)]. INA meldet nur die Anzahl der gelöschten Transitionen.

Abbildung 5.10: Reduktionen des Beispielnetzes 5.9
$\begin{figure}\fbox{\epsfbox{reduc_v.eps}}\end{figure}$

Im Beispiel 5.9 ergibt sich durch einmalige Anwendung der Regel das linke Netz des Beispiels 5.10. Zuerst wird die Transition t₀ geschaltet, bis die zwei Marken von p₀verbraucht sind. Dadurch liegen auf p₃ drei und auf p₄ zwei Marken. Als nächstes werden die Transition p₀, der Platz p₀ und die Transitionen t₁ und t₂ gelöscht und durch die Transitionen t₅ und t₆ ersetzt. Das Schalten von t₅im reduzierten Netz hat die gleiche Wirkung wie das Schalten von t₁ und das zweimalige Schalten von t₀ im alten Netz, genauso verhält es sich mit dem Schalten von t₆ und dem Schalten von t₂ und t₀.
Insgesamt wird die Regel dreimal angewendet, es ergibt sich daß rechte Netz des Beispiels 5.10. Im Session-Report finden Sie folgendes Protokoll:
transition elimination V:
t0,p0 deleted.
t1,p1 deleted.
t2,p2 deleted.

`<W>` DELETION of PTP-sequences

INA sucht eine Transition t und zwei Plätze p und q, die folgende Bedingungen genügen:

p ist der einzige Vorplatz, q der einzige Nachplatz von t, wobei $p\neq q$
t ist die einzige Vortransition von q und q besitzt Nachtransitionen
die Vielfachheit des Bogens von p nach t und von t nach q ist gleich eins
In solch einer Situation werden die Plätze p und q verschmolzen und die Transition t gelöscht.
Diese Transformation kann beschränkte bzw. nichtlebendige Netze in unbeschränkte bzw. lebendige Netze transformieren; ist also nur eingeschränkt anwendbar. Allerdings können Sie aus der Beschränkheit bzw. Nichtlebendigkeit des Reduktionsresultates auf die Beschränkheit bzw. Nichtlebendigkeit des ursprünglichen Netzes schließen. INA gibt die Warnung Non-liveness and boundedness are not preserved under this rule aus und bittet Sie um Bestätigung der Ausführung: Execute? Falls Sie diese Frage mit <N> beantworten, wird das Kommando nicht ausgeführt.

Abbildung 5.11: Ein mit <W> reduzierbares Netz und das Ergebnis (reduce_w.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_w.eps}}\end{figure}$

Das linke Netz des Beispiels 5.11 ist tot, da keine Transition schalten kann. Nach Reduktion mit <W> ergibt sich durch Löschen der Transition t₁ und Verschmelzen der Plätze p₀ und p₁ zu p₀ das rechte Netz. Dieses Netz ist nun lebendig, da die Transition t₂ immer schalten kann. Ein totes Netz ist also in ein lebendiges Netz transformiert worden!
INA meldet die Anzahl der gelöschten Transitionen und schreibt in den Session-Report eine erneute Warnung aus:
transition elimination W:
Boundedness and non-liveness are not preserved!

Nodes deleted:
p1, t1;

Next: 6. Analyse Up: 5. Reduktion Previous: 5.2 Hilfsfunktionen

© 1996-98 Prof. Peter H. Starke (starke@informatik.hu-berlin.de) und Stephan Roch (roch@...)

INA Handbuch Version 2.1 zuletzt geändert: 1998-03-24