PETRI NETS AND THEIR PROPERTIES - Modelling with Generalised Stochastic Petri Nets - page 39

P-semiflows and P-invariant relations — Let us define a | P | -component
weight column vector Y = [y 1 ,y 2 , ··· ,y |P| ] T , whose entries are natural num-
bers. Consider the scalar product between the row vector representing an
arbitrary marking M 0 , and Y (denoted M 0 · Y). If M[t i M 0 , then using

( 2.11) we can rewrite M 0 · Y as:

M 0 · Y = M · Y + C(.,t) T · Y

(2.13)

Obviously, if C(.,t) T · Y = 0, the weighted token count in the Petri net
(using the entries of Y as weights) is the same for M and M 0 . This means
that the weighted token count is invariant with respect to the firing of t.
More generally, if

C T · Y = 0 (2.14)

i.e., vector Y is an integer solution of the set of linear equations

C(.,t) T · Y = 0

∀ t ∈ T :

(2.15)

then, no matter what sequence of transitions fires, the weighted token count
does not change, and remains the same for any marking reachable from
any given initial marking M. The positive vectors Y that satisfy equation
( 2.14) are called the P-semiflows of the Petri net. Note that P-semiflows
are computed from the incidence matrix, and are thus independent of any
notion of (parametric) initial marking. Markings are only instrumental for
the interpretation of P-semiflows.
In the special case in which Y is a vector of all 1's, then the following relation
holds:

X

∀ t ∈ T :

C(p,t) = 0 (2.16)

p∈P

This implies that the total number of tokens in a marking is not affected by
the firing of a transition t: since this is true for all transitions t, the total
number of tokens is not affected by any firing sequence. We can thus con-
clude that in this net, given any initial marking M 0 , all markings reachable
from M 0 have the same total number of tokens.
If Y is an arbitrary vector of natural numbers, it can be visualized as a
bag of places in which p i appears with multiplicity y i . This leads to the

expression

X

∀ t ∈ T :

C(p i ,t) · y i = 0 (2.17)

p i ∈P

which identifies an invariant relation, stating that the sum of tokens in all
places, weighted by Y, is constant for any reachable marking, and equal to
M 0 · Y, for any choice of the initial marking M 0 . This invariant relation is
called a place invariant, or simply P-invariant.