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

PN models (and systems) in which the initial marking is disregarded, sim-
ply become bipartite graphs that define the structural or static component
of the models. This structural component of a PN model is what we called
Petri net. Many studies were devoted in recent years to the investigation
of the properties of Petri nets that may be proved directly from their struc-
ture. The interest in this topic is due to the fact that any property proved
structurally is valid for each possible PN system (or model) obtained from
the Petri net by superposing an arbitrary marking to it.
We now illustrate some techniques used to investigate structural properties:
they are called structural technique s 3 . We divide them into two classes: (1)
linear algebraic techniques, that work on a matrix description of the Petri
net called incidence matrix, and (2) graph analysis techniques, that work
directly on the bipartite graph description of the net.

2.5.1 Linear algebraic techniques

Definition 2.5.1 The incidence matrix C of a PN with m places and n
transitions is an m × n matrix whose entries are defined as

C(p,t) = O(t,p) − I(t,p) (2.9)

The entry C(p,t) of the incidence matrix C represents the (negative or
positive) change in the number of tokens in place p due to the firing of
transition t. In other words, the columns of C correspond to transitions, and
the rows of C correspond to places; the column corresponding to transition
t, C( · ,t) defines the state change in all places induced by the firing of t;
similarly the row corresponding to place p, C(p, · ) defines the change in the
marking of p induced by the firing of all transitions of the net.
If we consider the functions O and I as matrices of natural integers, then
we can simply write

C = O T − I T

(2.10)

where O T (I T ) denotes the transpose of matrix O (I).
Observe that inhibitor and test arcs do not influence the entries of C. This
is because inhibitor and test arcs do not induce changes in the token count
of places. Note also that, in the computation of C(p,t), input arcs from p
to t, and output arcs from p to t, “cancel out”. For example, the net in
Fig. 2.12( a) has the same incidence matrix as that in Fig. 2.12( b) if m = n,
as that in Fig. 2.12( c) if m > n, and as that in Fig. 2.12( d) if m < n. This

3 As opposed to state space or reachability techniques that will be considered later in
this chapter.