Abstract: This study proposes an algorithm for the decomposition approach of Petri nets based on indexes of places and analyzes the complexity of the given algorithm. The main data structures required and four key functions contained in the algorithm are firstly addressed. It is proved that the proposed decomposition algorithm is a polynomial-time algorithm.
INTRODUCTION
As models for physical systems, Petri nets are well suited to describe and analyze systems with concurrency, synchronization and conflicts (Murata, 1989; Zeng and Duan, 2007; Wang et al., 2000). However, with the increase of the node number in a Petri net, its structure will be more complex, so it is difficult to analyze the properties of the net system. Traditionally, in order to overcome this difficulty, some solutions including decomposition, reduction, composition and net operation are introduced by many researchers. Lee et al. (1987) gives several generalized reduction methods of Petri nets. In Esparza (1994), a set of reduction rules are proposed that make it possible to reduce all and only live and bounded free choice Petri nets to a circuit containing one place and one transition. The reduction algorithm is shown to require polynomial time in the size of the system. In Samir (1999), two analytical decomposition techniques are proposed for computing the transient state space solution of large stochastic PN (SPN) models of MINs and HINs. A large scale SPN model is partitioned into smaller submodels. These submodels are compressed and combined to calculate the entire net.
Recently, Zeng (2007) proposed a decomposition method for structure-complex Petri nets based on the indexes of places. This decomposition method is very useful for property analysis of structure-complex Petri nets since the structure of the decomposition net is well-formed (Zeng, 2007). The language and process relations are analyzed during the decomposition and present a method to obtain the language of a Petri net in and to present the process of a structure-complex Petri net respectively. However, only the decomposition method is presented for a Petri net based on the indexes of places in all the research results (Zeng, 2007). The decomposition algorithm especially a polynomial-time decomposition algorithm for a Petri net based on indexes of places is not addressed in earlier study (Zeng, 2007).
In this study, a decomposition algorithm is proposed for a Petri net based on indexes of places and analyzes the time complexity of the given algorithm. The main data structures required by the decomposition algorithm and the key functions contained in the algorithm are firstly addressed. Finally, a polynomial-time decomposition algorithm for a Petri net is proposed.
DECOMPOSITION OF A PETRI NET BASED ON THE INDEXES OF PLACES
To save space, it is assumed that the readers are familiar with the basic definitions of Petri nets (Murata, 1989; Zeng and Duan, 2007; Wang et al., 2000). Some of the essential terminology and notations related to this study are defined as follows. Convenient to define, it is supposed that K = ω and W = 1 in the Petri net. And also assume that the Petri net discussed in this study is finite and connected and is not an S-Net (Zeng, 2004).
Definition 1: (Zeng, 2007): Let Σ = (P,T; F,M0)
be a Petri net, a function f : P → {1,2,..., k} is said to be an
index function defined on the place set if ∀ p1, p2εP,
Definition 2: (Zeng, 2007): Let Σ = (P,T; F,M0) be a Petri net, f : P → {1,2,..., k} be the index function on the places of Σ. Perti net Σi = (Pi,Ti; Fi,M0i) (iε{1,2,..., k}) is said to be the decomposition net of Σ based on the index function f if Σi satisfies the following conditions.
(1) |
(2) |
(3) |
(4) |
Simply, Σi is said as the index decomposition net of Σ.
Definition 3: Zeng (2004): A Petri net Σ = (P,T;F,M0)
is an S-Net iff
Theorem 1: (Zeng, 2007): Let Σi = (Pi,Ti;Fi,M0i) (iε{1, 2,..., k}) be the index decomposition net based on index of place of a Petri net Σ = (P,T;F,M0), then Σi is an S-net.
A structure-complex Petri net is shown in Fig. 1. We use the decomposition method of Definition 2 to decompose Σ.
A function f is first defined on the place set such that f(p1) = f(p6) = 1, f(p2) = f(p3) = 2, f(p4) = f(p5) = f(p7) = 3. It can prove that f satisfies all the conditions in Definition 1. Based on the method of Definition 2, three index decomposition net systems Σ1, Σ2 and Σ3 are obtained and shown in Fig. 2. Obviously,Σ1, Σ2 and Σ3 are S-Nets.
More discussions about this decomposition method can be found by Zeng (2004, 2007). The decomposition results with the method of definition 2.2 are usually not unique.
| Fig. 1: | A Petri net |
| Fig. 2: | Three decomposition subnets of the Petri net shown in Fig. 1 |
With the results discussed by Zeng (2004, 2007), it is usually to take the case that k is with the minimal value as the best result. In the following sections, we will present a polynomial-time algorithm for the decomposition approach. Firstly, the main data structures and key functions contained in the algorithm will be addressed.
MAIN DATA STRUCTURES
Firstly, the main data structures to store each component of a Petri net are presented, including its flow relation, the input and output set of each transition, each place and its tokens.
Store of flow relation: Because any Petri net can be determined
by its input matrix and output matrix[1], we use output
and
Store of the input and output set of each transition: The input set and output set of each transition are stored by a one-dimension array with |S|+1 length, respectively. An Array at represents the input set of a transition t, while bt represents the output set of t, which are shown as followings. If a place si belongs to at (or bt), the (i+1)th position in at (or bt) will be set as 1, otherwise be set as 0.
Store of a set Xk(k = 1, 2...): The places with same indexes will be put into a set Xk (k = 1, 2...) and Xk(K = 1,2...) is stored by a one-dimension array with |S| length. If the (i)th position in Xk is set as 1, it means si belongs to Xk(k = 1,2...). Otherwise, the corresponding position will be set as 0.
Store of index of each place: The index of each place is stored by a one-dimension array with |S| length, Pk (k = 1, 2...). If the index of si is l, the corresponding position of si in will be set as l in Pk (k = 1, 2...).
Store of tokens: A one-dimension array with |S| length, Q will be used to store all the tokens in the places. If si contains l tokens, the corresponding position of si in Q will be set as l.
Store of a set Yu(u = 1, 2...): Another set Yu(u = 1, 2...) are used to store the places of each decomposition net. Yu(u = 1, 2...) is also represented by a one-dimension array with |S| length. If the (i)th position in Yu is set as 1, it means si belongs to Yu(u = 1, 2...) Otherwise, the corresponding position will be set as 0.
ALGORITHM DESIGN
The main point in the decomposition algorithm is to obtain the index
of each place. According to the index of each place, the decomposition
S-Nets can be obtained by the outface subnet of the places with same index.
At the initialization step of the algorithm, we put all the places into
set X1. For each place in X1, denoted by p, let
In the following step, we select a place p in Xl (l = 1, 2,...) such that λ[p] ≠ 0 and move p from Xl to Xl+1. If there is a place moved out, the value λ[p] for each place in Xl will be updated. If λ[p] for each place in Xl is not 0, the selecting and moving operations will be repeated on Xl; Otherwise, repeat the selecting and moving operations on Xl+1. After the selecting and moving operations on completed on all sets, the places in one set can be assigned with one same index.
Key functions: Firstly, four key functions contained in the decomposition algorithm are presented which are Mark (Xk), Move (Xk,y), Divide (Xk) and Outface (Yu).
Mark (Xk) //Obtain λ[p] for each place in Xk
INPUT: Xk
OUTPUT: λ[p] for each place in Xk
Move (Xk,y)// Move place y from Xk
to Xk+1
INPUT: Xk and place y
OUTPUT: Set Xk and Xk+1
Divide (Xk)//Divide Xk into Yj,
Yj+1, Yj+2...
INPUT: Xk
OUTPUT: Sets Yj, Yj+1, Yj+2...
Outface (Yj)//Output the outface subnet of places in
Yj
INPUT: Yj
OUTPUT: Outface subnet Nj
Polynomial-time decomposition algorithm: A polynomial-time decomposition
algorithm for Petri nets based on indexes of places is presented here.
INPUT: a Petri net
OUTPUT: Decomposition subnets of Σ
COMPLEXITY ANALYSIS OF THE ALGORITHM
Firstly, we analyze the complexity of four key functions required by the decomposition algorithm:
| • | In function Mark(Xk), each “if” loop executes finite number of judgments and assignments, so the time complexity is only related to the layers of loops. There are three “for” loops, so the time complexity of the full function is O(n2m), where n = |S| and m = |T|, and the same to the followings |
| • | In function Move(Xk, y), the worst case of step “Search y in Xk and delete y from Xk” is to go through the whole set Xk, so the time complexity of this function is only O (n) |
| • | In function Divide(Xk), from the number of layers of the “for” loops, it can be determined that the time complexity of this function is also O (n2 m) |
| • | In function Outface (Yj), each “if” loop executes
finite number of judgments and assignments, so its time complexity
is O (nm). In the main algorithm, because the inner “for” loop executes finite number of judgments and assignments, the time complexity of the first step is O(nm). In Step 2 and Step 3, there are n times for assignments, so the time complexity of Step 2 and Step 3 is O(n), respectively. The time complexity of Step 4 is actually same to that of the function Mark(Xk), so it is O(n2 m). In Step 5, the step “select y ∈ Xk such that λ[y] is not 0” is actually searching a place whose index is non-zero, so the worst time complexity of this step is O(n). The “if” loop is actually to go through the whole set Xk, so the time complexity of the inner “for” loop is O(n2 m). There are two outside layers of “for” loops, so the time complexity of Step 5 is O(n4 m). In Step 6, the inner function is Divide(Xk), the time complexity of this step is O(n3 m). The time complexity of Step 7 is mainly determined by the “for” loop and the function Outface(Yj), so the time complexity of this step is O(n2 m). In Step 8, there are n times for search and assignments, so the time complexity of this Step is O (n2) |
| • | According to the time complexity of each step in the main algorithm, the time complexity of the whole algorithm is O(nm+n+n+n2m+n4m+n3 m+n2m+n2) =O(n4m). Therefore, the algorithm proposed in this paper is a polynomial-time decomposition algorithm |
EXAMPLE
Take the Petri net in Fig. 1 as an example to show the implementation process of the algorithm proposed in the article.
Step 1: Assignment the input and output set of each transition
•t1 = {p1, p3}, •t2
= {p3, p5}, •t3 = {p2}
•t4 = {p4}, •t5
= {p6, p7}, t1• = {p2,
p6} t2• = {p4}, t3•
= {p3, p6}, t4• = {p3,
p7}, t5• = {p1, p5}.
Step 2: Put the number of tokens of each place to set M, so we get the set M = {p1(1), p2(0), p3(1), p4(0), p5(1), p6(0), p7(0)}
Step 3: Put all places of Σ into X1, then we get x1 = {p1, p2, p3, p4, p5, p6, p7}
Step 4: Assign mark to each place in X1. Let s(k) represent that the mark of place s is k, so we can obtain P1 = {p1(2), p2(1), p3(4), p4(0), p5(2), p6(3), p7(2)}
Step 5: Decompose the net. Choose one place p1 from X1 whose mark is non-zero, and move it to X2, so X2 = {p1}. Update the mark of each place in X1, and store them in P1, then P1 = {p2(1), p3(3), p4(0), p5(1), p6(3), p7(2)}. Continue selecting places from X1 and moving it to X2 . Without loss of generalization, place p2 whose mark is non-zero is chosen and moved to X2 , so X2 = {p1, p2}. Update the mark of each place in X1, so P1={p3(3), p4(0), p5(1), p6(2), p7(2)}. Select place p3 whose mark is non-zero, and move it to X2, so X2= {p1, p2, p3}. Update the mark of each place in X1, P1 = {p4(0), p5(0), p6(1), p7(1)}. Select place p6 and move it to X2 , so X2 = {p1, p2, p3, p6}. Update the mark of each place inX1 again, P1= {p4(0), p5(0), p7(0)}, so X1 = {p4, p5, p7}, and the selecting and moving operations on P1 have been finished. Next, repeat the selecting and moving operations on X2 such that X2 = {p1, p2, p3, p6}. Obtain the mark of each place in X2, and store them in P2, so P2 = {p1(1), p2(1), p3(2), p6(1)}. Select the place p1 whose mark is non-zero, and move it to X3, so X3 = {p1}. Update the mark of each place in X2, P2 = {p2(1), p3(1), p6(1)}. Select place p6 and move it to X3 so as to obtain X3 = {p1, p6}. Update the mark of each place in X2, P2 = {p2(0), p3(0)}, so X2 = {p2, p3}, and the selecting and moving operations on P2 have been finished. Next, repeat the selecting and moving operations on X3 such that X3 = {P1, P6}. To obtain the mark of each place in X3 and store them in P3, so P3 = {P1(0), P6(0)}. The selecting and moving operations on P3 have been finished, and the Step 5 is also finished
Step 6: To obtain connected subnets. Y1 = {P4, P5, P7}, Y2 = {P2, P3}, and Y3 ={P1, P6}
Step 7: Output the outface subnet. Firstly, we output the outface subnet of Y3. For place P1, if there is an edge which connects ti and P1, then there will be an edge connecting ti and P1. Repeat the processing on P6, then we get the subnet of Σ1. Using the same method, we can get the subnets of Σ2 and Σ3
Step 8: Output the tokens of each place in each subnet. Note that the number of tokens of each place of the original net has already been stored in the set M. p1 has one token in Σ1. In Σ2, p3 has one token and p5 has one token in Σ3
The output result of the whole algorithm is shown in Fig. 2.
CONCLUSION
In order to analyze properties of structure-complex Petri nets, the decomposition for a Petri net based on the indexes of places is a very convenient and useful approach. This study proposes an algorithm for the decomposition approach. The main data structures required and four key functions contained in the decomposition algorithm are addressed in details. It is proved that the proposed decomposition algorithm is a polynomial-time algorithm which provides methods for property analysis of structure-complex Petri nets.
ACKNOWLEDGMENTS
The research work presented in this study is supported by the National Science Foundation of China under Grant No. 60603090, 90718011 and 60673053, the Excellent Young Scientist Foundation of Shandong Province of China under Grant No. 2006BS01019 and the Taishan Scholar Program of Shandong Province.