Next: 6. Analysis Up: 5. Reduction Previous: 5.2 Auxiliary functions

5.3 Reduction procedures

`<F>` Fusion of congruent nodes

INA searches for either two places or two transitions which are connected with all other nodes of the net in exactly the same way, so-called parallel nodes [Sta90, Definition 9.3 (87)].

Figure 5.2: A net with two parallel places and transitions (reduce_f.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_f.eps}}\end{figure}$

Illustration 5.2 shows a net with two parallel places (p1 and p2) and two parallel transitions (t1 and t2).
You have to indicate directly the type of nodes to be investigated: Check places (P), transitions (T) or exit (E) ? After entering <P> or <T> to search for places or transitions, respectively, INA either states that no parallel nodes were found (No application possible!), or informs about how many nodes were deleted. Normally, always the nodes with the higher number are deleted. For parallel places, however, the place with the smaller number is deleted, if it contains more tokens [Sta90, Regel 3 (88)].

Figure 5.3: Reductions with respect to parallel nodes of the example net 5.2
$\begin{figure}\fbox{\epsfbox{reduc_f.eps}}\end{figure}$

When entering <P> , the net of example 5.2 becomes the net on the left of example 5.3. Since the place p₂ had a higher number as p₁, and p₁ did not contain more tokens than p₂, place p₂ has been deleted. If further reduced with <T> , the right net of example 5.3 results. The transition t₂ has been deleted, since it had a higher number than transition t₁.
In the session report, you find the following protocol:
Fuse:
p2 deleted
 1 place(s) deleted 
t2 deleted
 1 transition(s) deleted

`<M>` Merging of equivalent places

This command merges equivalent places of the net. Two places p₁ and p₂ are equivalent, if

each place possesses exactly one post-transition, t₁ and t₂, respectively,
the multiplicity of the arcs from p₁ to t₁ and from p₂ to t₂ equals 1, and
the transitions t₁ and t₂ are connected to all places different from p₁ and p₂ in exactly the same way [Sta90, Definition 9.4 (88)].

Figure 5.4: A net with equivalent places and their reduction (reduce_m.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_m.eps}}\end{figure}$

In the net of example 5.4, the places p₁ and p₂ are equivalent.
In case INA finds two equivalent places p₁ and p₂, place p₂ (with a higher number as p₁), as well as its post-transition t₂, are deleted, the tokens on p₂ are added onto p₁, and the arcs leading to p₂ are directed towards p₁ [Sta90, Regel 4 (89)].
The net on the right of example 5.4 is the result of the reduction of the net on the left. Place p₂ and its post-transition t₂ have been deleted, the token from p₂ has been placed on p₁, and the arc from t₄ to p₂ has been directed towards p₁.
In the session report, you find the following protocol:
Merge equivalent places:
Transition  2 deleted, Place 2 deleted

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

This command merges pre- and post-transitions. Here, pF denotes all post-transitions of the place p, and F(pF) all pre-places of the post-transitions of p. are the places p which are the only pre-places of their post-transitions.
A place with the following characteristics is sought:

p has k>0 pre-transitions $t_1,\ldots,t_k$
p has n>0 post-transitions $t_1',\ldots,t_n'$
no transition is both pre- and post-transition of p
at least one post-transition of p has a post-place
p is the only pre-place of its post-transitions
all arcs starting at p have the same multiplicity v

if p has exactly one post-transition (n=1), then all arcs ending at p have multiplicity divisible by v
if p has more than one post-transition (n>1), then all arcs ending at p have multiplicity v

Figure 5.5: A net which is reducible with <A> and the result (reduce_a.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_a.eps}}\end{figure}$

The place p₁ in the net on the left of example 5.5 satisfies the above conditions.
In case INA finds a place p that satisfies all conditions, appropriate transitions are fired, if necessary, to ensure that fewer than v tokens are on p. Then the pre-transitions $t_1,\ldots,t_k$ , the place p itself, and the post-transitions $t_1',\ldots,t_n'$ are deleted; instead, $k\cdot n$ new transitions t_i,j are inserted in such a way that firing t_i,j has the same effect as firing t_i followed by firing t_j' x times - where x is the multiplicity of the arc from t_i to p divided by v[Sta90, Regel 5 (90)]. INA states only the amount of deleted places.
In example 5.5, the net on the right results. Place p₁ and the transitions t₁,t₂, and t₄ have been deleted and replaced by the transitions t₅ and t₆. Firing t₅ in the reduced net has the same effect as firing t₄ and t₁ in the old net, and similarly, t₆ is fired instead of t₄ and t₂.
In the session report, you find the following protocol:
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

This command merges a pre-transition with post-transitions. Here, Fp denotes all pre-transitions of the place p, and Fp(F) all post-places of the pre-transitions of p. are the places p which are the only post-places of their pre-transitions.
A place with the following characteristics is sought:

p has exactly one pre-transition t₀, and p is the only post-place of this transition
p has n>0 post-transitions $t_1',\ldots,t_n'$
no transition is both pre- and post transition of p
t₀ is the only post-transition of its pre-places
all arcs starting and ending at p have the same multiplicity v, and there are less than v tokens on p

Figure 5.6: A net which is reducible with <B> and the result (reduce_b.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_b.eps}}\end{figure}$

The place p₃ in the net on the left of example 5.6 satisfies the above conditions.
In case INA finds a place which satisfies all conditions, the pre-transition t₀, the place p itself, and the post-transitions $t_1',\ldots,t_n'$ are deleted; instead, n new transitions $t_1,\ldots,t_n$ are inserted in such a way that firing t_j has the same effect as firing t₀ followed by firing t_j'[Sta90, Regel 6 (92)]. INA states only the amount of deleted places.
In example 5.6, the net on the right results. Place p₃ and the transitions t₀, t₁, and t₂ have been deleted and replaced by the transitions t₅ and t₆. Firing t₅ in the reduced net has the same effect as firing t₀ and t₁ in the old net, and similarly, t₆ is fired instead of t₀ and t₂.
In the session report, you find the following protocol:
place elimination B:
Transition 5 replaces transitions 1 * 0
Transition 6 replaces transitions 2 * 0
Place 3 deleted

`<C>` ELIMINATION of looping places

This command searches for bounded and unbounded places that satisfy the following conditions:

each transition t subtracts at most as tokens from p as it adds to p
p is sufficiently marked.
Place p will be deleted, if there are no isolated transitions as a result. INA states the amount of deleted places.

Figure 5.7: A net with a reducible looping place (reduce_c.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_c.eps}}\end{figure}$

In the net of example 5.7, the place p₁ satisfies the above conditions, and is therefore deleted.
When you start to reduce with this command, INA asks the question Shall we delete only bounded places?. If you answer <Y> , only bounded places will be deleted, otherwise also unbounded places. A place p is unbounded, if firing a transition t adds more tokens to p than are subtracted from p, and the transition t is live, i.e., p is adequately marked.
If, in the net of example 5.7, the multiplicity of the arc from t₁ to p₁ is increased by one to two, then the place p₁ is unbounded, and therefore it will not be deleted, if you have answered the question with <N> .
In the session report, you find the following protocol:
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

This command deletes all transitions t that satisfy the following conditions:

firing t does not alter the marking
a different transition t' exists which - in order to be enabled - requires at least as many tokens on each pre-place of t as t does.
This situation is described as a loop. In case INA finds such a transition, it is deleted. INA states the amount of deleted transitions.

Figure 5.8: A net with a reducible loop (reduce_u.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_u.eps}}\end{figure}$

A simple example for a loop is net 5.8. Firing transition t₁ does not alter the marking of the net. Since the transition t₂ subtracts at least as many tokens as t₁ from p₁, t₁ is deleted.
In the session report, you find the following protocol:
transition elimination U:
transition 1 deleted

`<V>` DELETION of single output transitions

This command merges a pre-place with post-places. A transition with the following characteristics is sought:

t has exactly one pre-place p
the multiplicity of the arc from p to t is one
p has k>0 pre-transitions $t_1,\ldots,t_k$
p is not a post-place of t, but t has post-places

Figure 5.9: A net which is reducible with <V> (reduce_v.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_v.eps}}\end{figure}$

The transition t₀ of the net in example 5.9 satisfies the above conditions.
In case INA finds a transition which satisfies all conditions, t is fired repeatedly until p contains no more tokens. Then the transition t, the place p, and the pre-transitions $t_1,\ldots,t_k$ are deleted; instead, k new transitions $t_j^\star$ are inserted in such a way that firing $t_j^\star$ has the same effect as firing t_j followed by firing $t_j^\star$ x times -- where x is the multiplicity of the arc from t_j to p. INA states only the amount of deleted places.

Figure 5.10: Reduction of Example net 5.9
$\begin{figure}\fbox{\epsfbox{reduc_v.eps}}\end{figure}$

In example 5.9, a single application of this rule yields the net on the left of example 5.10. First, the transition t₀ is fired until the two tokens on p₀ have left. This implies that there are three tokens on p₃ and two on p₄ then. Next, the transition p₀, the place p₀, and the transitions t₁ and t₂ are deleted and replaced by transitions t₅ and t₆. Firing t₅ in the reduced net has the same effect as firing t₁ and firing twice t₀ in the old net, and similarly, t₆ is fired instead of t₂ and t₀.
Altogether, the rule is applied three times, yielding the net on the right in example 5.10.
In the session report, you find the following protocol:
transition elimination V:
t0,p0 deleted.
t1,p1 deleted.
t2,p2 deleted.

`<W>` DELETION of PTP-sequences

INA searches for a transition t and two places p and q, which satisfy the following conditions:

p is the only pre-place, q the only post-place of t, where $p\neq q$
t is the only pre-transition of q, and q possesses post-transitions
the multiplicity of the arcs from p to t and from t to q equals one.
In such a situation, the places p and q are merged, and the transition t is deleted.
This transformation can transform bounded or non-live nets into unbounded or live nets, respectively; its application is therefore limited. However, you can deduce from the boundedness or non-liveness of the reduction result the boundedness or non-liveness of the original net. INA warns Non-liveness and boundedness are not preserved under this rule, and requests you to confirm the execution: Execute? If you answer this question with <N> , the command will not be executed.

Figure 5.11: A net which is reducible with <W> and the result (reduce_w.pnt)
$\begin{figure}\fbox{\epsfbox{reduce_w.eps}}\end{figure}$

The net on the left in example 5.11 is dead, since no transition can fire. After reducing with <W> , the deletion of the transition t₁ and the merging of the place p₁ into p₀ yield the net on the right. This net is now live, since the transition t₂ can always fire. Hence, a dead net has been transformed into a live net!
INA states the amount of deleted transitions, and writes another warning in the session report:
transition elimination W:
Boundedness and non-liveness are not preserved!

Nodes deleted:
p1, t1;

Next: 6. Analysis Up: 5. Reduction Previous: 5.2 Auxiliary functions

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

INA Manual Version 2.2 (last changed 1999-04-19)