Information Technology Reference
In-Depth Information
Step 3
. Decompose
N
R
into subnets, each of which contains no conflict
place.
Step 4
. Check each of the decomposed net derived from Step 3 to
decide whether it is a feasible solution.
The following discussions focus on the decomposition procedure
of Step 3.
The branches after each conflict place represent options from
which we can choose for data processing. A snippet of RSN is shown
in Figure 3.8. Place
p
1
is a conflict place. Hence, data type
a
attached
to
p
1
can be processed by operation
t
1
or
t
2
,ortheXORjoinof
operations
f
t
32
g
.
An RSN must be decomposed into a set of subnets that do not
contain any conflict places. Simply speaking, each time a conflict place
is encountered, one branch is selected as the active one, and the other
branches are removed. As Figure 3.8 illustrates, three subnets are
generated because
p
1
has three succeeding transitions (
t
31
and
t
32
are grouped and treated as one single branch).
When there are more than one conflict place in an RSN, the
decomposition is more complicated. If there are
n
conflict places
each with
m
branches, possibly we have
m
n
distinctive subnets. This
clearly shows the exponential growth of subnets, which is the worst-
case scenario. We use
selection tuple
to decide which branch to choose
for each conflict place. One selection tuple corresponds to one situation
of decomposition, and we use
Decomposition Algorithm
to obtain one
subnet for each evaluation. Now, we give function definitions before a
decomposition algorithm is given.
t
31
;
a
t
1
b
t
1
b
p
1
a
t
2
c
c
t
2
p
1
a
a
1
t
31
a
1
t
31
a
p
1
t
32
a
2
p
1
t
32
a
2
Figure 3.8
Illustration of the decomposition algorithm.
