Graphics Programs Reference
In-Depth Information
to visit next [p r ]).
We shall see that P-invariants are very useful for the reduction of the GSPN
model.
A first consequence of the P-invariants is that place p r is vanishing: the three
immediate transitions (t a ,t q ,t s ) that remove tokens from p r have two input
places each: p r and one among p a ,p q ,p s ; because of the P-invariant covering
the three places, at least one of them is marked in any possible system state,
so that at least one of the three immediate transitions is enabled when p r is
marked.
Since p r is vanishing, T w is the only timed transition in the model whose
firing causes an immediate transition to become enabled. Indeed, when T a
(T s ) fires, t q (t a ) is not enabled because p r cannot be marked.
The algorithms presented in Chapter 6 reduce a subnet of immediate tran-
sitions by including them into the timed transitions whose firing can cause
that of an immediate transition in the subset. The rigorous application of
the algorithm to our example would therefore require that t a ,t q and t s be
included into T a ,T s , and T w , but considering that the firing of T a and T s
cannot enable any immediate transition, as explained above, we only have
to include t a ,t q , and t s into T w .
Transitions t a , t q and t s form a non-free-choice conflict, so that all possible
combinations of enabled and disabled transitions must be considered, as
described in Chapter 6.
If we concentrate on the firing of T w followed by t a , four cases are possible,
that correspond to four new transitions whose names are in parentheses:
t a is the only enabled transition (T wa1 ), t a is enabled with t q (T wa2 ), t a is
enabled with t s (T wa3 ), and t a is enabled with both t q and t s (T wa4 ).
Similar sets of replicas exist for t q and t s .
The resulting net is shown in Fig. 9.9, where one timed and three immediate
transitions have been replaced by twelve timed transitions, and the vanishing
place p r has been removed. The states of this SPN are isomorphic to the
tangible states of the GSPN model in Fig. 9.8, so that the total number of
states has been reduced at the price of cluttering the resulting SPN with
timed transitions and arcs.
Fig. 9.9 is where the reduction algorithm leads us, but we can again exploit
the modeller's ingenuity and familiarity with the model, and in particular
the knowledge of P-invariants, to greatly simplify the net.
A first important observation is that all transitions in the same set of replicas
modify the SPN marking in the same way, as they actually correspond to
the firing of the same transition.
Let's write the rates of the transitions in the first set of replicas. Denoting
by W(T x ) the rate of transition T x , we have
= M(p w ) ω M(p a )
M(p a )
W(T wa1 )
=
 
Search WWH ::




Custom Search