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)

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 des Beispielnetzes 5.2 bezüglich paralleler Knoten

Das Netz des Beispiels 5.2 wird durch Eingabe von <P> zum linken Netz des Beispiels 5.3. Da der Platz eine größere Nummer als hat und nicht mehr Marken als enthält, wird der Platz gelöscht. Wird weiter mit <T> reduziert, so ergibt sich das rechte Netz des Beispiels 5.3. Die Transition wird gelöscht, da sie eine größere Nummer als die Transition 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 und sind äquivalent, wenn

• beide Plätze je genau eine Nachtransition bzw. besitzen,
• die Vielfachheit der Bögen von zu bzw. von zu gleich 1 ist und
• die Transitionen bzw. mit allen von und 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)

Im Netz des Beispiels 5.4 sind die Plätze und äquivalent.

Falls INA zwei äquivalente Plätze und findet, so werden der Platz (mit einer höheren Nummer als ) sowie seine Nachtransition gestrichen, die auf befindlichen Marken zusätzlich auf gelegt und die nach führenden Bögen nach geführt [Sta90, Regel 4 (89),].

Das rechte Netz des Beispiels 5.4 zeigt die Reduktion des linken Netzes. Der Platz und seine Nachtransition werden gelöscht, die Marke von wird auf gelegt und der Bogen von zu wird nach geführt.

Im Session-Report finden Sie folgendes Protokoll:

Merge equivalent places:
Transition  2 deleted, Place 2 deleted

<A> ELIMINATION of -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
• p hat n>0 Nachtransitionen
• 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)

Der Platz 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 , der Platz p selbst und die Nachtransitionen gestrichen, dafür werden neue Transitionen so eingeführt, daß ein Schalten von die gleiche Wirkung wie ein Schalten von gefolgt von x-maligem Schalten von , wobei x die Vielfachheit des Bogens von 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 und die Transitionen , und werden gelöscht und durch die Transitionen und ersetzt. Das Schalten von im reduzierten Netz hat die gleiche Wirkung wie das Schalten von und im alten Netz, genauso verhält es sich mit dem Schalten von und dem Schalten von und .

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 -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 und p ist der einzige Nachplatz dieser Transition.
• p hat n>0 Nachtransitionen
• keine Transition ist zugleich Vor- und Nachtransition von p
• 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)

Der Platz 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 , der Platz p selbst und die Nachtransitionen gestrichen, dafür werden n neue Transitionen so eingeführt, daß ein Schalten von die gleiche Wirkung wie ein Schalten von gefolgt von einem Schalten von [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 und die Transitionen , und werden gelöscht und durch zwei Transitionen und ersetzt. Das Schalten von im reduzierten Netz hat die gleiche Wirkung wie das Schalten von und im alten Netz, genauso verhält es sich mit dem Schalten von und dem Schalten von und .

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)

Im Netz des Beispiels 5.7 erfüllt der Platz 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 nach um eins auf zwei erhöht wird, dann ist der Platz 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)

Ein einfaches Beispiel für eine Schleife zeigt das Netz 5.8. Das Schalten der Transition ändert die Markierung des Netzes nicht. Da die Transition mindestens so viele Marken von abzieht wie , wird 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
• p ist kein Nachplatz von t, aber t hat Nachplätze

Abbildung 5.9: Ein mit <V> reduzierbares Netz (reduce_v.pnt)

Die Transition 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 gestrichen, dafür werden k neue Transitionen so eingeführt, daß ein Schalten von die gleiche Wirkung wie ein Schalten von gefolgt von x-maligem Schalten von , wobei x die Vielfachheit des Bogens von nach p ist [Sta90, Regel 9 (95),]. INA meldet nur die Anzahl der gelöschten Transitionen.

Abbildung 5.10: Reduktionen des Beispielnetzes 5.9

Im Beispiel 5.9 ergibt sich durch einmalige Anwendung der Regel das linke Netz des Beispiels 5.10. Zuerst wird die Transition geschaltet, bis die zwei Marken von verbraucht sind. Dadurch liegen auf drei und auf zwei Marken. Als nächstes werden die Transition , der Platz und die Transitionen und gelöscht und durch die Transitionen und ersetzt. Das Schalten von im reduzierten Netz hat die gleiche Wirkung wie das Schalten von und das zweimalige Schalten von im alten Netz, genauso verhält es sich mit dem Schalten von und dem Schalten von und .

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
• 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)

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 und Verschmelzen der Plätze und zu das rechte Netz. Dieses Netz ist nun lebendig, da die Transition 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;