Subscribe Now Subscribe Today
Research Article
 

Analysis of Structure properties of Petri Nets Using Transition Vectors



Farooq Ahmad, Huang Hejiao and Wang Xiaolong
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

This study introduces transition vectors based on place transitive matrix derived from graph theory, to study the structure of Petri nets using structure theoretical results that exists in Petri net theory. It has been established that transition vectors provide a simplified and more adequate approach than transitive matrix towards the structural analysis of PN. Some structural classes of Petri nets have been decided and basic concepts about the structure of Petri net have been derived through novel idea of transition vectors. Firstly new representation of place transitive matrix has been introduced for acyclic Petri nets. Secondly Petri net structure has been analyzed and an algorithm to find a directed cycle has been presented with a simplified representation, using transition vectors. Thirdly transition vectors have efficiently been used to identify the particular structures of Petri nets. Finally, useful concepts relevant to the structure of Petri nets have been derived.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Farooq Ahmad, Huang Hejiao and Wang Xiaolong, 2008. Analysis of Structure properties of Petri Nets Using Transition Vectors. Information Technology Journal, 7: 285-291.

DOI: 10.3923/itj.2008.285.291

URL: https://scialert.net/abstract/?doi=itj.2008.285.291

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 place-transition 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 easier-to-investigate 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, self-loop free PNs and restricted PNs defined by Peterson (1981). But some important structural sub-classes 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 place-transition 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 = {p1, p2, ..., p|P|} is a finite set of places, |P|>0; T = {t1, t2, ..., 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 (tj) represents the set of input place(s) of transition tj ε T, then place pi ε P is an input place of a transition ti if pi ε I (tj); O (tj) represents the set of output place(s) and pi is an output place of tj if pi ε O (tj). Incoming arc to tj is represented by (pi, I (tj)) and outgoing arc from tj be (pi, O (tj)). The input and output functions can be extended to map set of places P into the set of transitions T. Then arc (tj, I (pi)) represents the incoming arc to pi as tj ε I(pi) and arc (tj, O (pi)) represents outgoing arc from pi as tj ε O (pi) ∀ tj ε T, ∀pi ε 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: (Self-loop-free PN) A PN structure N = (P, T, I, O) is said to be self-loop-free or pure if and only if j ε T, I(tj)∩O(tj) = φ i.e., no place may be both an input and an output of the same transition.

Definition 3: (State-machine) A PN structure N is said to be state-machine if and only if j ε T, |I(tj)| = 1 =|O(tj)| i.e., every transition tj ε 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 (pi)| = 1 = |O(pi)| i.e., for every place pi ε P, there exist one and only one input transition and one and only one output transition.

Definition 5: (Free-choice Petri net) PN N is said to be free-choice Petri net if and only if i ε P, ∀tj ε T, either I(tj) = {pi} or O (pi) = {tj}.

Definition 6: (Asymmetric choice PN) an asymmetric choice Petri net is a PN N such that i, pj ε P: O (pi) ∩ O (pj) ≠… Ø ⇒ (O (pi) ⊆ O (pj) ∨ O (pj) ⊆ O (pi)).

Definition 7: (Matrix definition of PN structure) A PN N = (P, T, B-,B+) where B- and B+ are |P|x|T| matrices of input and output functions, respectively, defined by: B- [I, j] = 1 , if there is an arc (pi. I (tj)) or 0 otherwise. B+ [i, j] = 1, if there is an arc (pi, O(tj)) 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

given as , Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors and . Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

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 xi ∈ P∪T: ∀i = 1,....,k and set of k-1 arcs,Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors 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 xi, xj ∈ P∪T, there is a path either from xi to xj or from xi to xj i.e., one of them is reachable from other. A PN is said to be strongly connected if any node xi ∈ P∪T is reachable from any other node xj ∈ P∪T. A connected PN is strongly connected if and only if for each directed arc (xi, xj) there is a directed path leading from xi to xj.

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors
Fig. 1: Different petri net models; (a) without source and sink transition (b) with sink transition and (c) source transition

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors
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 Dp = (VP, EP) (or DT = (VT, ET)) for PN N is called a place (or transition) transitive graph, where VP = P (or VT = T) is the set of vertices and EP = T (or ET = P) is the set of directed arcs and is input transition (or place) of pi (orti) and the output transition (or place) of place pj (ortj), 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 verticesImage for - Analysis of Structure properties of Petri Nets Using Transition Vectors 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

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors and . Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

Then Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsand Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsare the place transitive matrix and transition transitive matrix, respectively.

Definition 11: (Labeled place transitive matrix) Let Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsbe the labeled place transitive matrix, defined by Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors, where ti Image for - Analysis of Structure properties of Petri Nets Using Transition VectorsrepresentImage for - Analysis of Structure properties of Petri Nets Using Transition Vectors the labels. The entry in the ith row and jth column as means the transitive relation from input place pi (row i) to the output place pj (column j) through firing of the transition tk.

But Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsof PN having source or/and sink transition(s) can not include all the transitions appearing in the structure of PN. If tj ∈ T is a source transition of given Petri net such that I (tj) = Ø and pi ∈ O (tj) is the output place of source transition tj, then all the entries of ith column of Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsare zero. Similarly if tj be a sink transition in PN as O (tj) = Ø and pi ∈ I (tj), then all the entries of ith row of Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors 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. 1a-c all have the same transitive matrix i.e., Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors .

In order to overcome the vague representation of place transitive matrix of Petri net having source or/and sink transition(s), new representation of Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsis suggested. This advantageous representation admits all the transitions of PN model to appear in Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors, provides the complete place-transition 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 tj such that Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsthen the first entry of ith zero column (row) of transitive matrix will be labeled as Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors.

The example of new representation of place transitive matrix of PNs in Fig. 1b and c can be shown as

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors and , Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors respectively.

Property 2: Let N be a PN having |P|x|P| labeled place transitive matrix Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors, then

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

is a row |P|-vector of transitions and

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

is a column |P|-vector of transitions. Transition vector TR is mapping as Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorswhere I:P→T is input function; T C is a mapping where Image for - Analysis of Structure properties of Petri Nets Using Transition VectorsImage for - Analysis of Structure properties of Petri Nets Using Transition Vectorswhere O:P → T is output function. So ith component of TR which is TR (pi) gives the set of input transitions of place pi and ith component TC (pi) is a set of output transitions of place pi.

The components of TR and TC are finite linear combinations of transitions with positive integer coefficients. Coefficients of transitions appearing in transition vector TR (TC) 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 TR (TC) can be interpreted as source place pi (sink place pi) such as I (pi) = Ø (O (pi) = Ø). Labeled zero component e.g., 0/tj appearing in transition vector TR (TC) indicates the zero incoming arc to (outgoing arc from) tj and hence tj 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 TR (TC) e.g., transitions vectors TR and TC of PN in Fig. 1c can be written as TR = [0/t0 0/t0 t1+t2] and TC = [t1 t2 0]T, where first and second component of TR which is 0/t0 indicate the zero indegree of transition t0 i.e., source transition while third zero component of TC communicates p3 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 TR or/and TC has at least one zero component (labeled or/and unlabeled). As explained for property 2, zero component(s) of TR or/and TC correspond to source or/and sink place(s), respectively; labeled zero component(s) of TR or/and TC 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 TR and TC are non-zero. 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 self-loop free or pure if and only if the corresponding same components TR (pi) and TC (pi) don’t have identical transition k ∈ T such that tk ∈ TR (pi) and tk ∈ TC (pi) ∀ i = 1, 2,....,|P|. In words, if different transition(s) are appearing in each corresponding same components of both TR and TC then PN structure is said to be self-loop 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 TRor/and TC must have at least one zero (labeled or/and unlabeled) component. Choose any node x1 ∈ P∪T, if x1 is a source place e.g., pi ∈ P (transition e.g., tk ∈ T), then ith component of TR will be zero (labeled zero), otherwise there will be a transition tk ∈ TR (pi) such that tR ∈ I (pi) (pi ∈ O (tk)). Similarly, by scanning other entries of TR, there must be source place (transition). Now, choose any other node x2 ∈ P∪T, if x2 is sink place e.g., pj ∈ P (transition tS ∈ T), then jth component of TC will be zero (labeled zero), otherwise there will be a transition tS ∈ TC (pj), such that tS ∈ O (pj), (pj ∈ I (tS),). Similarly, scanning other entries in TC, there must be sink place (transition).

Property 7: Every self-loop free cyclic PN is strongly connected.

Proof: By property 4 Cyclic PN, every entry of transition vectors TR and TC must have at least one transition. As no transition and place of PN is on a self-loop. So it is possible to leave any place pi ∈ P through

an arc (pi I (tj)) such as tj ∈ TC (pi) and to enter any place pk ∈ P through an arc (pk O (tj)) such as tj ∈ TR (pk). So there exist directed path from any node xi ∈ P∪T to any other node xj ∈ P∪T. These arguments establish the statement of the property.

Property 8: A cyclic PN having place pi ∈ P on self-loop is strongly connected iff ith entry of transition vector TC has at least two transitions or/and the transition on self-loop with pi has coefficient at least 2.

Proof: Suppose that place pi ∈ P is on self-loop with transition tj ∈ T in the strongly connected cyclic PN N. So by property 5, ∃tj ∈ TR (pi) and tj ∈ TR (pi). By definition of strongly connectedness, there must be a directed path from any node xi ∈ P∪T to any other node xj ∈ P∪T. Firstly, we can not leave place pi ∈ P through an arc (pi, I (tj)) as pi is on a self-loop with tj. The condition of strongly connectedness is violated if we don’t have an arc (pi, I (tk) such that tk ∈ TC (pi) other than tj ∈ TC (pi). So, ith component of transitions vector TC must have at least two transitions. Secondly, we can not leave tj which is on a self-loop, as there is only one out going arc from tj to self-loop place pi, which violates the strongly connectedness condition. So, tj must have coefficient at least 2 which indicates the outdegree of tj at least 2, in order to find directed path from self-loop to any node of N. So both or one of these two are necessary conditions for strongly connectedness.

Conversely, suppose pi ∈ P on a self-loop with tj ∈ T in cyclic PN N, ith component of TC has at least one transition other than tj ∈ TC (pi) or/and tj has coefficient at least 2. Then we can leave place pi through transition tk ∈ TC (pi) other than tj ∈ TC (pi) or/and tj can be left to enter a place other than pi. As given PN is cyclic having no zero entry in transition vectors TR and TC, so from property 7, there exist directed path from any node xi ∈ P∪T to any other node xi ∈ 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 TR and TC both have all non-zero components. As all entries of TC have at least one transition, so each place is the input of at least one transition i.e., pi ∈ I (tj) such that tj ∈ TC (pi) ∀ i = 1, 2,...,|P| and ∀ j = 1, 2,...,|T|. All entries of TR also have at least one transition such that pi ∈ O (tj), tj ∈ TR (pi) ∀ i = 1, 2,...,|P| and ∀ j = 1, 2,...,|T|. Then we can leave every node xi ∈ P∪T through its outgoing arc and can enter to every node xj ∈ 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.

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors
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 TR and TC.

(1)
Select ith entry of TC i.e., TC (pi) 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 TC.
(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 TR to locate selected transition in step 3 and select transition in first component having selected transition.
(ii)
Select an entry (place) in TR 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 TR and TC obtained from transitive matrix , given by TR = [t5 t1 t2 t3+t4] and TC = [t1+t2 t3 t4 t5].

First entry of TC corresponds to place p1, having transitions t1 and t2 in the first component of TC. After selecting t1, second component of TR contains t1 whichcorresponds to second entry i.e., p2, getting directed path p1 → t1 → p2. Augmenting the iterations of algorithm, directed cycle is given by p1 → t1 → p2 → t3 → p4 → t5 → p1. Similarly, the directed cycle p1 → t2 → p3 → t4 → p4 → t5 → p1 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 TR and TC are efficiently used to identify these structural sub-classes 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

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors
Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

In words, If every component of TR and TC 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 Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors; i.e., single transition (not necessarily distinct) is appearing in all components of transition vectors TR and TC, then PN structure is called as marked graph.

Note: # (TR(pi)) (respectively, # (TC(pi)) is the number of transitions in ith component of TR, (respectively, TC).

Property 12: A PN N is said to be a conflict free or persistent if and only if

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors
If Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorssuch that Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsthen Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

In words, a structure is said to be a conflict free Petri net if and only if every component of TC has at most one transition, or if any component of TC has more than one transition then these transitions must appear in the corresponding same component of TR. A PN structure has conflict or choice if at least one component of vector TC has more than one transition. For TC having multiple transitions at ith entry, provided self-loop exception of place pi 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

Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors

In words, if all the transitions of ith component are included in jth component of TC or all the transitions of jth component are included in the ith component of TC , 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 Tc has coefficient 2 or greater than two. If every component of TC 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 Image for - Analysis of Structure properties of Petri Nets Using Transition Vectorsand Image for - Analysis of Structure properties of Petri Nets Using Transition Vectors. A PN structure having BPP is called BPP-net (Esparza and Nielsen, 1994).

For example, all the components of both the transition vectors TR and TC of PN model shown in Fig. 3 are non-zero and no corresponding same entries of TR and TC have identical transition, so given PN structure is cyclic and self-loop free. Property 7 implies that given PN is strongly connected. As all components of transition vectors TR and TC are distinct transition(s), so state-machine structure of PN having basic parallel process (BPP) must be identified. First component of transition vector TC has two transitions i.e., #(TC(p1)) = 2 such as t1, t2 ∈ TC(pi). Property 12 implies that transitions t1 and t2 are on conflict or have choice to fire when p1 is marked. So, either firing sequence (t1t3) or (t2t4) 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 place-transition 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 marking-independent 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 High-Tech R and Dprogram (863 Program) under grant No. 2006 AA01Z197.

REFERENCES

1:  Amer-Yahia, C., N. Zerhouni, A.E. Moudni and M. Ferney, 1999. Some subclasses of petri nets and the analysis of their structural properties: A new approach. IEEE. Trans. Syst. Man Cybernetics-Part A., 29: 164-172.
CrossRef  |  

2:  Best, E., 1986. Structure theory of petri nets: The free choice hiatus. Lecture Notes Comput. Sci., 254: 168-205.
CrossRef  |  

3:  Cai, Y., T. Sekiguchi, H. Tanaka, M. Hikichi and Maruyama, 1993. A method for structural analysis of petri net models. Proceedings of the 19th Conference on IECON'93, November 15-19, 1993, Maui, HI., USA., pp: 133-137
CrossRef  |  

4:  Esparza, J. and M. Nielsen, 1994. Decidability issues for petri nets: A survey. J. Inform. Process. Cybernet. EIK., 30: 143-160.
Direct Link  |  

5:  Itoh, Y., I. Miyazawa and J. Liu, 1999. On analysis of petri net properties based on transitive matrix. Proceeding of the IECON, November 29-December 3, 1999, Location: San Jose, CA., USA., pp: 973-978
CrossRef  |  

6:  Lee, J.K., 2002. Decomposition of petri nets using the transitive matrix based on P-invariant. Proceedings of the Systems, Man and Cybernetics, Volume 3, October 6-9, 2002, IEEE Xplore, pp: 6-6
CrossRef  |  

7:  Lee, J., 2005. A Scheduling Analysis in FMS Using the Transitive Matrix. LNAI 3397, Springer-Verlag, Berlin, pp: 167-178.

8:  Lee, J. and O. Korbaa, 2006. Scheduling analysis of FMS: An unfolding timed petri nets approach. Math. Comput. Simulat., 70: 419-432.
CrossRef  |  

9:  Liu, J., Y. Itoh, I. Miyazawa and T. Sekiguchi, 1999. A research on petri net properties using transitive matrix. Proceedings of the Systems, Man and Cybernetics, August 6, 1999, Tokyo, Japan, pp: 888-893
CrossRef  |  

10:  Miyazawa, I., H. Tanaka and T. Sekiguchi, 1996. Classification of solutions of matrix equation related to parallel structure of a petri net. Proceedings of the Conference on Emerging Technologies and Factory Automation, Volume 2, November 18-21, 1996, Kauai, HI., USA., pp: 446-452
CrossRef  |  

11:  Miyazawa, I., Y. Itoh and T. Sekiguchi, 1998. A result on the relationship between petri net and directed graph: Real time fault diagnosis based on petri net model. Proceedings of the 24th Annual Conference of IECON, August 31-September 4, 1998, Aachen, Germany, pp: 126-131

12:  Murata, T., 1989. Petri nets: Properties, analysis and applications. Proc. IEEE., 77: 541-580.
CrossRef  |  Direct Link  |  

13:  Peterson, J., 1981. Petri Net Theory and the Modeling of Systems. 1st Edn., Prentice Hall, Englewood Cliffs, New Jersey, ISBN: 0136619835, pp: 288

14:  West, D.B., 2001. Introduction to Graph Theory. 2nd Edn., Pearson Education, Inc., London

15:  Zurawski, R. and M.C. Zhou, 1994. Petri nets and industrial applications: A tutorial. IEEE. Trans. Ind. Elect., 41: 567-583.
CrossRef  |  

©  2021 Science Alert. All Rights Reserved