INTRODUCTION
Petri Nets (PNs) are promising mathematical and graphical tool for
modeling, analysis and design of information processing systems. Petri
nets have been frequently used to model and analyze systems that are characterized
as being distributed, parallel, concurrent, asynchronous nondeterministic,
having discrete events, conflicts, deadlocks or resource sharing (Zurawski
and Zhou, 1994; Murata, 1989; Peterson, 1981). Petri nets have a power
to analyze the modeled system revealing important information about structure
and dynamic behavior of system and same model can be used for performance
evaluation. Petri net method for the specification and verification of
systems is becoming more and more important as systems increase in size
and complexity.
The structural analysis of PN depicts useful information about the behavior
of modeled system and the structure of underlying net. Since PN corresponds
in a natural way to a directed graph, so the static structure of PN facilitates
to study structural i.e., graph theoretic properties depending on the
placetransition relationship of underlying net by the flow relation.
The study of structure of PNs has the objectives to increase their modeling
power and to study the underlying properties of model. The structural
analysis of PN has advantage over reachability tree method which exhibit
state space explosion problem for larger and concurrent systems. Using
structural analysis, important information about the behavior of the modeled
system can be achieved. The behavioral properties that are of foremost
interest and less easily analyzable in the analysis of systems may be
reduced to easiertoinvestigate structural properties (Best, 1987). Parallel
and cycle structure of PN has been used for classification of solution
of matrix equation in order to obtain the firing count vector as a solution
of matrix equation (Miyazawa et al., 1996). Up till now, no broad
structural classification of PNs has been decided instead of general PNs,
ordinary PNs, selfloop free PNs and restricted PNs defined by Peterson
(1981). But some important structural subclasses of PN have been investigated
in the literature (Best, 1987; Murata, 1989; Amer et al., 1999).
Place and transition invariant method has been used to investigate the
structural properties of the underlying unmarked net by Murata (1989).
The relationship between PN structure and directed graph has also been
discussed and result has been described for a cycle structure of PN (Miyazawa
et al., 1998). A method for structural analysis of PN model using
transition invariants has been proposed by Cai et al. (1993). Authors
identify the cycle or/and parallel structure by the solutions of the homogeneous
equations of transition invariants. However, study of some basic properties
such as boundedness and liveness etc., through structural analysis of
PNs is still to be investigated.
Transitive matrix depicts all the placetransition relationships and
entries of transitive matrix describe the transferring relation from one
place to another place through transitions. The characteristic polynomial
equation of transitive matrix has been proposed to identify the cyclic
structure in PNs (Itoh et al., 1999). Transitive matrix method
has also been introduced to study the behavioral properties of PN model
(Itoh et al., 1999; Liu et al., 1999). Transitive matrix
has been used for decomposition and slicing the basic unit of concurrency
in PN model (Lee and Korbaa, 2005; Lee, 2005, 2002).
In this study, new concept of transition vectors to represent and analyze
the structure o f PN has been proposed. Transition vectors provide a simplified
approach to describe the structure of PN and all the information relevant
to the structure. New representation of transitive matrix has also been
suggested. Some important concepts relevant to structure and classes of
PN have been verified using transition vectors.
BASIC DEFINITIONS AND CONCEPTS
Here, some basic definitions, notations, structural classification
of ordinary PN (for the sake of simplicity) and its matrix representation
are described. The related terminology and notations are mostly taken
from (Peterson, 1981; Murata, 1989). Directed and transitive graphs are
also explained. The concepts and terminology related to graph theory are
taken from (West, 2001).
Definition 1: (Petri net structure) A Petri net structure N,
is a four tuple, N = (P, T, I, O) where P = {p_{1}, p_{2},
..., p_{P}} is a finite set of places, P>0; T = {t_{1},
t_{2}, ..., t_{T}} is a finite set of transitions, T>0;
I: T → P^{∞} is the input function, a mapping indicating
the directed arcs from places to transitions; O: T → P^{∞}
is the output function, a mapping indicating the directed arcs from transitions
to places, P∩T = φ and P∪T ≠ φ.
Let I (t_{j}) represents the set of input place(s) of transition
t_{j} ε T, then place p_{i} ε P is an input
place of a transition t_{i} if p_{i} ε I (t_{j});
O (t_{j}) represents the set of output place(s) and p_{i}
is an output place of t_{j} if p_{i} ε O (t_{j}).
Incoming arc to t_{j} is represented by (p_{i}, I (t_{j}))
and outgoing arc from t_{j} be (p_{i}, O (t_{j})).
The input and output functions can be extended to map set of places P
into the set of transitions T. Then arc (t_{j}, I (p_{i}))
represents the incoming arc to p_{i} as t_{j} ε I(p_{i})
and arc (t_{j}, O (p_{i})) represents outgoing arc from
p_{i} as t_{j} ε O (p_{i}) ∀ t_{j}
ε T, ∀p_{i} ε P.
There exists classification of the topological structure of PN having
specific characterizations. The following definitions of structural subclasses
of PN are due to (Peterson, 1981; Murata, 1989).
Definition 2: (Selfloopfree PN) A PN structure N = (P, T, I,
O) is said to be selfloopfree or pure if and only if _{j} ε
T, I(t_{j})∩O(t_{j}) = φ i.e., no place may be
both an input and an output of the same transition.
Definition 3: (Statemachine) A PN structure N is said to be statemachine
if and only if _{j} ε T, I(t_{j}) = 1 =O(t_{j})
i.e., every transition t_{j} ε T has exactly one input place
and exactly one out put place.
Definition 4: (Marked graph) A marked graph is a PN N such that
_{i} ε P, I (p_{i}) = 1 = O(p_{i}) i.e.,
for every place p_{i} ε P, there exist one and only one input
transition and one and only one output transition.
Definition 5: (Freechoice Petri net) PN N is said to be
freechoice Petri net if and only if _{i} ε P, ∀t_{j}
ε T, either I(t_{j}) = {p_{i}} or O (p_{i})
= {t_{j}}.
Definition 6: (Asymmetric choice PN) an asymmetric choice Petri
net is a PN N such that _{i}, p_{j} ε P: O (p_{i})
∩ O (p_{j}) ≠… Ø ⇒ (O (p_{i}) ⊆
O (p_{j}) ∨ O (p_{j}) ⊆ O (p_{i})).
Definition 7: (Matrix definition of PN structure) A PN N = (P,
T, B^{},B^{+}) where B^{} and B^{+}
are PxT matrices of input and output functions, respectively, defined
by: B^{} [I, j] = 1 , if there is an arc (p_{i}. I (t_{j}))
or 0 otherwise. B^{+} [i, j] = 1, if there is an arc (p_{i},
O(t_{j})) or 0 otherwise. The incidence matrix B is defined by
B = B^{+}–! B^{}. For example, matrix of input
function B^{}, matrix of out put function B^{+} and incidence
matrix B of PN in Fig. 1c are, respectively
Definition 8: (Graph and directed graph); A graph G = (V, E)
consists of a set V of vertices and a set E of edges. If E is set of directed
arcs, G is called a directed graph or digraph denoted by D.
Since PN corresponds to a directed graph, so the following concepts are
taken directly from graph theory and explained in the context of PNs.
A directed path is a set of k nodes x_{i} ∈ P∪T: ∀i
= 1,....,k and set of k1 arcs,
the ith arc connects the ith node to (i+1)th node. The directed cycle
is a directed path from one node back to itself. PN structure has two
important types of connectivity, intensively studied to explain and verify
many basic properties of system modeled by PN i.e., connected PNs and
strongly connected PNs. A PN is simply connected if, for any pair of nodes
x_{i}, x_{j} ∈ P∪T, there is a path either from
x_{i} to x_{j }or from x_{i }to x_{j}
i.e., one of them is reachable from other. A PN is said to be strongly
connected if any node x_{i} ∈ P∪T is reachable from any
other node x_{j} ∈ P∪T. A connected PN is strongly connected
if and only if for each directed arc (x_{i}, x_{j}) there
is a directed path leading from x_{i} to x_{j}.

Fig. 1: 
Different petri net models; (a) without source and sink
transition (b) with sink transition and (c) source transition 

Fig. 2: 
(a) The place transitive graph of Fig.
1c (b) The transition transitive graph of Fig. 1c 
Definition 9: (Transitive graph) A directed graph
D_{p} = (V_{P}, E_{P}) (or D_{T} =
(V_{T}, E_{T})) for PN N is called a place (or transition)
transitive graph, where V_{P} = P (or V_{T} = T) is the
set of vertices and E_{P} = T (or E_{T} = P) is the set
of directed arcs and is input transition (or place) of p_{i} (ort_{i})
and the output transition (or place) of place p_{j} (ort_{j}),
respectively. For example, Fig. 2a shows the place transitive
graph and Fig. 2b is a transition transitive graph for
PN model shown in Fig. 1c.
TRANSITION VECTORS
Here, definitions of transitive matrix and labeled place transitive
matrix are presented which are based on (Itoh et al., 1999; Liu
et al., 1999). New representation of place transitive matrix and the
idea of transition vectors are also being introduced in order to analyze
the structure of PN.
Definition 10: (Transitive matrix) Let V = P∪T be the set
of vertices
and the set of directed arcs. D = (V, E) is a directed graph of the PN
N. The adjacent matrix A and transitive matrix S are

and . 

Then and
are
the place transitive matrix and transition transitive matrix, respectively.
Definition 11: (Labeled place transitive matrix) Let be
the labeled place transitive matrix, defined by ,
where t_{i} represent
the labels. The entry in the ith row and jth column as means the transitive
relation from input place p_{i} (row i) to the output place p_{j}
(column j) through firing of the transition t_{k}.
But of
PN having source or/and sink transition(s) can not include all the transitions
appearing in the structure of PN. If t_{j} ∈ T is a source
transition of given Petri net such that I (t_{j}) = Ø and
p_{i} ∈ O (t_{j}) is the output place of source transition
t_{j}, then all the entries of ith column of are
zero. Similarly if t_{j} be a sink transition in PN as O (t_{j})
= Ø and p_{i} ∈ I (t_{j}), then all the entries
of ith row of
are zero. So place transitive matrix representation of PN having source
or/and sink transition(s) does not give the complete portrait of PN model
e.g., PNs in Fig. 1ac all have the same transitive matrix
i.e., .
In order to overcome the vague representation of place transitive matrix
of Petri net having source or/and sink transition(s), new representation
of is
suggested. This advantageous representation admits all the transitions
of PN model to appear in ,
provides the complete placetransition relationship for PN having source
or/and sink transition(s) and accommodating the synthesis to Petri net
model.
Property 1:If Petri net N has source (sink) transition t_{j}
such that then
the first entry of ith zero column (row) of transitive matrix will be
labeled as .
The example of new representation of place transitive matrix of PNs in
Fig. 1b and c can be shown as

and , 

respectively. 
Property 2: Let N be a PN having PxP
labeled place transitive matrix ,
then
is a row Pvector of transitions and
is a column Pvector of transitions. Transition vector T_{R}
is mapping as where
I:P→T is input function; T _{C} is a mapping where where
O:P → T is output function. So ith component of T_{R} which
is T_{R} (p_{i}) gives the set of input transitions of
place p_{i} and ith component T_{C} (p_{i}) is
a set of output transitions of place p_{i}.
The components of T_{R} and T_{C} are finite linear combinations
of transitions with positive integer coefficients. Coefficients of transitions
appearing in transition vector T_{R} (T_{C}) represents
number of incoming arcs i.e., indegree or number of input places (number
of outgoing arcs called outdegree or number of output places) of transitions.
The ith zero component of transition vector T_{R} (T_{C})
can be interpreted as source place p_{i} (sink place p_{i})
such as I (p_{i}) = Ø (O (p_{i}) = Ø). Labeled
zero component e.g., 0/t_{j} appearing in transition vector T_{R}
(T_{C}) indicates the zero incoming arc to (outgoing arc from)
t_{j} and hence t_{j} stands for source (sink) transition.
As the first labeled zero entry(ies) of zero column(s) (zero row(s)) belong
only to zero column(s) (zero row(s)) of transitive matrix, therefore they
can only be added to T_{R} (T_{C}) e.g., transitions vectors
T_{R} and T_{C} of PN in Fig. 1c can
be written as T_{R} = [0/t_{0} 0/t_{0} t_{1}+t_{2}]
and T_{C} = [t_{1} t_{2} 0]^{T}, where
first and second component of T_{R} which is 0/t_{0} indicate
the zero indegree of transition t_{0} i.e., source transition
while third zero component of T_{C} communicates p_{3}
as sink place.
ANALYSIS OF STRUCTURE PROPERTIES OF PN USING TRANSITIONS VECTORS
Here, some structural classes and fundamental properties about the
structure of PN are presented in terms of transition vectors in order
to analyze the structure of PN. An algorithm to find a directed cycle
is also presented.
Property 3: A PN N is acyclic if its transition vectors T_{R}
or/and T_{C} has at least one zero component (labeled or/and unlabeled).
As explained for property 2, zero component(s) of T_{R} or/and
T_{C} correspond to source or/and sink place(s), respectively;
labeled zero component(s) of T_{R} or/and T_{C} correspond
to source or/and sink transition(s), respectively. So PN structure is
said to acyclic if it has at least one source or/and sink place (or/and
transition). An acyclic PN does not imply that it can never contain a
cycle.
Property 4: A PN N is cyclic if and only if all the components
of both the transition vectors T_{R} and T_{C} are nonzero.
This condition refers to the situation that there is neither any source
and sink place nor any transition in the PN structure. In words, the structure
of PN will be cyclic if it doesn’t have any source and sink place (and
transition).
Property 5: A PN N is selfloop free or pure if and only if the
corresponding same components T_{R} (p_{i}) and T_{C}
(p_{i}) don’t have identical transition _{k} ∈ T
such that t_{k} ∈ T_{R} (p_{i}) and t_{k}
∈ T_{C} (p_{i}) ∀ i = 1, 2,....,P. In words,
if different transition(s) are appearing in each corresponding same components
of both T_{R} and T_{C} then PN structure is said to be
selfloop free.
Property 6: Every acyclic PN has at least one sink place (transition)
and at least one source place (transition).
Proof: Since N is acyclic, so by property 3 its transition vectors
T_{R}or/and T_{C} must have at least one zero (labeled
or/and unlabeled) component. Choose any node x_{1} ∈ P∪T,
if x_{1} is a source place e.g., p_{i} ∈ P (transition
e.g., t_{k} ∈ T), then ith component of T_{R} will
be zero (labeled zero), otherwise there will be a transition t_{k}
∈ T_{R} (p_{i}) such that t_{R} ∈ I
(p_{i}) (p_{i} ∈ O (t_{k})). Similarly, by
scanning other entries of T_{R}, there must be source place (transition).
Now, choose any other node x_{2} ∈ P∪T, if x_{2}
is sink place e.g., p_{j} ∈ P (transition t_{S} ∈
T), then jth component of T_{C} will be zero (labeled zero), otherwise
there will be a transition t_{S} ∈ T_{C} (p_{j}),
such that t_{S} ∈ O (p_{j}), (p_{j} ∈
I (t_{S}),). Similarly, scanning other entries in T_{C},
there must be sink place (transition).
Property 7: Every selfloop free cyclic PN is strongly connected.
Proof: By property 4 Cyclic PN, every entry of transition vectors
T_{R} and T_{C} must have at least one transition. As
no transition and place of PN is on a selfloop. So it is possible to
leave any place p_{i} ∈ P through
an arc (p_{i} I (t_{j})) such as t_{j} ∈
T_{C} (p_{i}) and to enter any place p_{k} ∈
P through an arc (p_{k} O (t_{j})) such as t_{j}
∈ T_{R} (p_{k}). So there exist directed path from
any node x_{i} ∈ P∪T to any other node x_{j}
∈ P∪T. These arguments establish the statement of the property.
Property 8: A cyclic PN having place p_{i} ∈ P on
selfloop is strongly connected iff ith entry of transition vector T_{C}
has at least two transitions or/and the transition on selfloop with p_{i}
has coefficient at least 2.
Proof: Suppose that place p_{i} ∈ P is on selfloop
with transition t_{j} ∈ T in the strongly connected cyclic
PN N. So by property 5, ∃t_{j} ∈ T_{R} (p_{i})
and t_{j} ∈ T_{R} (p_{i}). By definition
of strongly connectedness, there must be a directed path from any node
x_{i} ∈ P∪T to any other node x_{j} ∈ P∪T.
Firstly, we can not leave place p_{i} ∈ P through an arc
(p_{i}, I (t_{j})) as p_{i} is on a selfloop
with t_{j}. The condition of strongly connectedness is violated
if we don’t have an arc (p_{i}, I (t_{k}) such that t_{k}
∈ T_{C} (p_{i}) other than t_{j} ∈ T_{C}
(p_{i}). So, ith component of transitions vector T_{C}
must have at least two transitions. Secondly, we can not leave t_{j}
which is on a selfloop, as there is only one out going arc from t_{j}
to selfloop place p_{i}, which violates the strongly connectedness
condition. So, t_{j} must have coefficient at least 2 which indicates
the outdegree of t_{j} at least 2, in order to find directed path
from selfloop to any node of N. So both or one of these two are necessary
conditions for strongly connectedness.
Conversely, suppose p_{i} ∈ P on a selfloop with t_{j}
∈ T in cyclic PN N, ith component of T_{C} has at least one
transition other than t_{j} ∈ T_{C} (p_{i})
or/and t_{j} has coefficient at least 2. Then we can leave place
p_{i} through transition t_{k} ∈ T_{C} (p_{i})
other than t_{j} ∈ T_{C} (p_{i}) or/and t_{j}
can be left to enter a place other than p_{i}. As given PN is
cyclic having no zero entry in transition vectors T_{R} and T_{C},
so from property 7, there exist directed path from any node x_{i}
∈ P∪T to any other node x_{i} ∈ P∪T. Hence the
given cyclic PN is strongly connected.
Property 9: If N be a PN without any source and sink place (and
transition), then there is a directed cycle in N.
Proof: According to the property 4, N given in the statement of
property is cyclic which implies that transition vectors T_{R}
and T_{C} both have all nonzero components. As all entries of
T_{C} have at least one transition, so each place is the input
of at least one transition i.e., p_{i} ∈ I (t_{j})
such that t_{j} ∈ T_{C} (p_{i}) ∀
i = 1, 2,...,P and ∀ j = 1, 2,...,T. All entries of T_{R}
also have at least one transition such that p_{i} ∈ O (t_{j}),
t_{j} ∈ T_{R} (p_{i}) ∀ i = 1, 2,...,P
and ∀ j = 1, 2,...,T. Then we can leave every node x_{i}
∈ P∪T through its outgoing arc and can enter to every node x_{j}
∈ PT through its incoming arc. So, we stop as soon as we obtain a
repeated node in directed path getting directed cycle and give the proof
of the statement.

Fig. 3: 
An example of PN model 
Directed cycles play a key role in the structure theory and analysis
of modeled systems by PNs. The existence of directed cycle in the PN structure
assists in verifying important structural properties. An algorithm is
presented in order to find directed cycles in the cyclic PN structure
using transition vectors.
Algorithm to find a directed cycle: INPUT: Transition vectors
T_{R} and T_{C}.
(1) 
Select ith entry of T_{C} i.e., T_{C}
(p_{i}) for i = 1 
(2) 
If selected place is same as previously selected place then, Go
to step 6, else go to next step. 
(3) 
Do 
(i) 
Select first transitions in the ith component of T_{C}. 
(ii) 
If selected transition is same as previously selected transition
then go to step 6, else go to next step. 
(4) 
Do 
(i) 
Scan all components of T_{R} to locate selected transition
in step 3 and select transition in first component having selected
transition. 
(ii) 
Select an entry (place) in T_{R} corresponding to selected
transition in step 4(i) 
(5) 
Go to step 2 
(6) 
OUT PUT: Directed cycle. 
(7) 
END 
The algorithm given can efficiently be used to find directed cycle in
cyclic PN. For example PN model given in Fig. 3, has
transition vectors T_{R} and T_{C} obtained from transitive
matrix , given by T_{R} = [t_{5} t_{1} t_{2}
t_{3}+t_{4}] and T_{C} = [t_{1}+t_{2}
t_{3} t_{4} t_{5}].
First entry of T_{C} corresponds to place p_{1}, having
transitions t_{1} and t_{2} in the first component of
T_{C}. After selecting t_{1}, second component of T_{R}
contains t_{1} whichcorresponds to second entry i.e., p_{2},
getting directed path p_{1} → t_{1} → p_{2}.
Augmenting the iterations of algorithm, directed cycle is given by p_{1}
→ t_{1} → p_{2} → t_{3} →
p_{4} → t_{5} → p_{1}. Similarly, the
directed cycle p_{1} → t_{2} → p_{3}
→ t_{4} → p_{4} → t_{5} →
p_{1} can be obtained using above mentioned algorithm.
IDENTIFICATION OF PARTICULAR STRUCTURES USING TRANSITION VECTORS
Certain PNs have structural characteristics and properties not possessed
by the other PN structures. In this section, transition vectors T_{R}
and T_{C} are efficiently used to identify these structural subclasses
of PNs.
Property 10: PN structure is said to be state machine if and only
if there does not exists any transition t ∈ T such that
• 

• 

In words, If every component of T_{R} and T_{C} is a
distinct transition(s), then state machine structure of PN can be identified.
Property 11: A PN N is said to be a marked graph if and only if
;
i.e., single transition (not necessarily distinct) is appearing in all
components of transition vectors T_{R} and T_{C}, then
PN structure is called as marked graph.
Note: # (T_{R}(p_{i})) (respectively, # (T_{C}(p_{i}))
is the number of transitions in ith component of T_{R}, (respectively,
T_{C}).
Property 12: A PN N is said to be a conflict free or persistent
if and only if
In words, a structure is said to be a conflict free Petri net if and only
if every component of T_{C} has at most one transition, or if any
component of T_{C} has more than one transition then these transitions
must appear in the corresponding same component of T_{R}. A PN structure
has conflict or choice if at least one component of vector T_{C}
has more than one transition. For T_{C} having multiple transitions
at ith entry, provided selfloop exception of place p_{i} with these
transitions, the case corresponds to the situation of conflict.
Property 13: A PN structure is said to be simple Petri net if
and only if
In words, if all the transitions of ith component are included in jth
component of T_{C} or all the transitions of jth component are
included in the ith component of T_{C} , then simple PN structure
can be identified.
PN structure represents to have concurrent or parallel activity if and
only if at least one entry of vector T_{c} has coefficient 2 or
greater than two. If every component of T_{C} of PN structure
has distinct transition(s) i.e., every transition t ∈ T has exactly
one input place, then PN structure has Basic Parallel Process (BPP). In
formal way, there does not exist t ∈ T such that and
.
A PN structure having BPP is called BPPnet (Esparza and Nielsen, 1994).
For example, all the components of both the transition vectors T_{R}
and T_{C} of PN model shown in Fig. 3 are nonzero
and no corresponding same entries of T_{R} and T_{C} have
identical transition, so given PN structure is cyclic and selfloop free.
Property 7 implies that given PN is strongly connected. As all components
of transition vectors T_{R} and T_{C} are distinct transition(s),
so statemachine structure of PN having basic parallel process (BPP) must
be identified. First component of transition vector T_{C} has
two transitions i.e., #(T_{C}(p_{1})) = 2 such as t_{1},
t_{2} ∈ T_{C}(p_{i}). Property 12 implies
that transitions t_{1} and t_{2} are on conflict or have
choice to fire when p_{1 }is marked. So, either firing sequence
(t_{1}t_{3}) or (t_{2}t_{4}) can occur.
CONCLUSION
In this study, novel concept of transition vectors has been introduced
to analyze the structure of PN. It has been shown that transition vectors
provide complete information about the structure of PNs is symmetrical
manner as they are bijection of the set of places P to their sets of input
and output transitions which can not be observed in transitive matrix.
Some structural classes of PNs have been decided and basic concepts about
the structure of PN have been established by using the simplified approach
of transition vectors. Simple algorithm to find a directed cycle in PN
structure has been presented using transition vectors. Transition vectors
have efficiently been used to identify the structural subclasses of PNs.
New representation of place transitive matrix for acyclic PN has also
been introduced which provides the complete list of transitions and elaborate
the placetransition relationship in transitive matrix, whenever acyclic
PN have source or/and sink transition(s). It has been established that
transition vectors provide a simplified and more adequate approach than
transitive matrix towards the analysis and depiction of important properties
of PN structure. Some fundamental markingindependent properties of PN
model of system e.g. boundedness, liveness and conservativeness etc, will
be studied using transition vectors.
ACKNOWLEDGMENTS
This research was financially supported by National Natural Science
Fund of China with grant No. 10701030 and grant No. 60435020 and National
HighTech R and Dprogram (863 Program) under grant No. 2006 AA01Z197.