Research Article
A Polynomial-time Decomposition Algorithm for Petri Nets Based on Indexes of Transitions
College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao 266510, China
As models for physical systems, Petri nets are well suited to describe and analyze systems with concurrency, synchronization and conflicts (Murata, 1989; Zeng, 2004; Zeng and Duan, 2007; Wang and Zeng, 2008). 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. Decomposition of Petri nets is one of very useful methods for property analysis of structure-complex systems. Kwang et al. (1987) gave several generalized reduction methods of Petri nets. In Koriem (1999), two analytical decomposition techniques are proposed for computing the transient state space solution of large Stochastic Petri Net (SPN) models of Multistage Interconnection Networks (MINs) and Hierarchical Interconnection Networks (HINs). A large scale SPN model is partitioned into smaller submodels. The submodels are compressed and combined to calculate the entire net. In Esparza (1994), many reduction rules are introduced 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 Zeng (2007), two decomposition methods are proposed for structure-complex Petri nets based on the indexes of places and transitions, respectively. The decomposition methods proposed in Zeng (2007) are very useful for property analysis of structure-complex Petri nets since the structure of the decomposition net is well-formed by Zeng (2007, 2008) and Cui et al. (2011). The language and process relations are analyzed during the decomposition and a method is proposed to present the process of a structure-complex Petri net (Zeng, 2008), respectively. However, we only presented the decomposition method for a Petri net based on the indexes of places or transitions in the previous research results (Zeng, 2007, 2008; Cui et al., 2011).
To find a decomposition algorithm especially a polynomial-time decomposition algorithm for a Petri net is also as important as the decomposition method. Unlike the traditional work on Petri net decomposition (Kwang et al., 1987; Koriem, 1999; Esparza, 1994; Zeng, 2007), this study addresses a polynomial-time algorithm for Petri net decomposition. Recently, we presented a polynomial-time algorithm was presented for the decomposition approach based on indexes of places (Zeng et al., 2008). This study gives a decomposition algorithm for a Petri net based on indexes of transitions and analyzes the complexity of the given algorithm. The main data structures and key functions contained in the algorithm will be addressed in detail. It is proved that the proposed decomposition algorithm is a polynomial-time algorithm. It provides a useful computation method for the decomposition of structure-complex Petri nets.
DECOMPOSITION OF A PETRI NETS BASED ON THE INDEXES OF TRANSITIONS
Some of the essential terminology and notations related to this study are defined first. To save space, more concepts of Petri nets can be seen (Murata, 1989; Zeng 2004; Zeng and Duan, 2007; Wang and Zeng, 2008). Convenient to define, we assume that the Petri nets discussed in this study are finite and connected and they are not T-Nets (Murata, 1989; Zeng, 2004; Zeng and Duan, 2007; Wang and Zeng, 2008).
Definition 1: Let Σ = (S, T; F, M0) be a Petri net, a function f: T → {1, 2, ..., k} is said to be an index function defined on the transition set if:
f (t) is named as the index of the transition t (Zeng, 2007).
Definition 2: Let Σ = (S, T; F, M0) be a Petri net, f: T → {1, 2, ..., k} be the index function on the transitions of Σ. The Petri net Σi = (Si, 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 (Zeng, 2007).
(1) |
(2) |
(3) |
(4) |
where, ΓS → Si M0 is the projection of M0 such that:
Simply, Σi is named as the index decomposition net of Σ.
Definition 3: A Petri net Σ = (S, T; F, M0) is a T-Net iff (Zeng, 2007).
Theorem 1: Let Σ = (Si, Ti; Fi, M0i) (I∈{1, 2, ..., k}) be the decomposition net based on index of transition of a Petri net Σi = (S, T; F, M0), then Σi is a T-net (Zeng, 2007).
Proof: In the decomposition nets Σi = (Si, Ti; Fi, M0i) (i∈{1, 2, ..., k}), we assume that there is at least one net is not a T-net. Without loss of generality, let Σj = (Sj, Tj; Fj, M0j) (1≤j≤k) be not a T-net. Because Σj = (Sj, Tj; Fj, M0j) is not a T-net, there is at least one place S∈Sj such that |CS|>1 or |S•*>1 according to the definition of T-net.
• | In the case |•S|>1, it means that the place s has at least two input transitions. Without loss of generality, we assume that the input transitions of s are t1 and t2, thus: |
• | According to Definition 1, f(t1)≠f(t2). According to Definition 2 t1 and t2 should be decomposed into two subnet, so t1 and t2 can not be the input transitions of s in Σj = (Sj, Tj; Fj, M0j). Thus, the assumption is not correct |
• | In the case |S•|>1, the conflict can also be obtained using the similar proof process. Therefore, in the decomposition nets (Σj = (Sj, Tj; Fj, M0j) (i∈{1, 2, ..., k}) there is no any net is not a T-net. The theorem is proved |
The Petri net shown in Fig. 1 is the model for the problem of the dining philosophers. We use the decomposition method of Definition 2 to decompose Σ.
Fig. 1: | The Petri net model for the problem of the dining philosophers |
Fig. 2: | The decomposition subnets of the Petri net shown in Fig. 1 |
A function f is first defined on the place set such that:
It can prove that f satisfies all the conditions in Definition 1. Based on the method of Definition 2, five index decomposition net systems Σ1, Σ2, Σ3, Σ4 and Σ5 are obtained. Each Σi(i = 1, 2, 3, 4, 5) is shown in Fig. 2. The semantic of the decomposition approach is clear. We can see that each Σi(i = 1, 2, 3, 4, 5) shown in Fig. 2 is the model for one philosopher.
More discussion about the decomposition approach based on the indexes of transitions can be seen by Zeng (2007). Based on the results presented by Zeng (2007), to find a polynomial-time algorithm for the decomposition approach is the future work to be addressed. In the following sections, we present a polynomial-time algorithm for the decomposition approach. Firstly, the main data structures and key functions contained in the algorithm are addressed first.
MAIN DATA STRUCTURES
Firstly, the main data structures to store the components 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 (Murata, 1989), we use output matrix:
and input matrix:
to represent the structure of a Petri net, where,
can be stored by a two-dimension array, respectively.
Store of the input and output set of each place: The input set and output set of each place are stored by a one-dimension array with |T|+1 length, respectively. An Array as represents the input set of a place s, while bs represents the output set of s, which are shown as followings. If a place ti belongs to as (or bs), the (i+1)th position in as (or bs) will be set as 1, otherwise be set as 0.
Store of a set Xk (k = 1, 2 ): The transitions 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 |T| length. If the (i)th position in Xk is set as 1, it means ti belongs to Xk(k = 1, 2 ). Otherwise, the corresponding position will be set as 0.
Store of index of each transition: The index of each transition is stored by a one-dimension array with |T| length, Pk (k = 1, 2 ). If the index of ti is l, the corresponding position of ti in Q 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 transitions of each decomposition net.Yu (u = 1, 2 ) is also represented by a one-dimension array with |T| length. If the (i)th position in Yu is set as 1, it means ti 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 transition. According to the index of each transition, the decomposition net can be obtained transaction with same index. At the intialization step of the algorithm, we put all the transition s into set X1. For each transition in X1, denoted by t, let:
In the following step, we select a transition t in Xl (l = 1, 2, ...) such that λ[t]≠0 and move t from Xl to Xl+1. If there is a transition moved out, the value λ[t] for each transition in Xl will tions with same index. At the initialization step of the be updated. If λ[t] for each transition in Xl is not equal to 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 transitions 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 transition in Xk |
• | Move(Xk, y)// Move transition y from Xk to Xk+1 INPUT: Xk and transition 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 transitions in Yj INPUT: Yj OUTPUT: outface subnet Nj |
A polynomial-time decomposition algorithm: Now we present a polynomial-time decomposition algorithm for Petri nets based on indexes of transitions.
• | INPUT: a Petri net Σ = (N, M) = (S, T; F, M0) OUTPUT: Decomposition subnets of Σ |
COMPLEXITY ANALYSIS OF THE ALGORITHM
Firstly, we analyze the complexity of four key functions required by the decomposition algorithm.
• | Step 1: 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 (m2n), where n = |S| and m = |T| and the same to the followings |
• | Step 2: 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 (m) |
• | Step 3: 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 (m2n) |
• | Step 4: 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, there are n times for assignments, so the time complexity of Step 2 is O (n).In step 3, the time complexity is O (m).The time complexity of step 4 is actually same to that of the function Mark (Xk), so it is O (m2n). 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 (m). The if loop is actually to go through the whole set Xk, so the time complexity of the inner for loop is O (m2n). There are two outside layers of for loops, so the time complexity of step 5 is O (m4n). In step 6, the inner function is Divide (Xk) and the time complexity of this step is O (m3n). 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 (m2n). In step 8, there are n times for search and assignments, so the time complexity of this step is O (m2n).
According to the time complexity of each step in the main algorithm, the time complexity of the whole algorithm is O (nm + n + m + m2n + m4n + m3n + m2n + m2n) = O (m4n). Therefore, the algorithm proposed in this study is a polynomial-time decomposition algorithm.
EXAMPLE
We take the Petri net for the problem of the dining philosophers in Fig. 1 as an example to show the implementation process of the algorithm proposed in the study.
Step 1: Assignment the input and output set of each place.
Step 2: Put the number of tokens of each place to set M, so we get the set M = {p11 (1), p12 (1), p13 (0); p21 (1), p22 (1),p 23(0); p31 (1), p32 (1), p33 (0); p41 (1), p42 (1), p43 (0); p51 (1), p52 (1), p53 (0)}.
Step 3: Put all transitions of Σ into X1, then we get X1 = {t11, t21; t21, t22; t31, t32; t41, t42 ;t51, t52}
Step 4: Assign mark to each place in X1. Let t (k)represent that the mark of transition t is k, so we can obtain P1 = {t11 (2), t12 (2); t21 (2), t22 (2); t31 (2), t32 (2); t41 (2), t42 (2); t51 (2), t52 (2)}.
Step 5: Decompose the net. Choose one transition t21 from X1 whose mark is non-zero and move it to X2, so X2 = {t21}. Update the mark of each transition in X1and store them in P1, then, P1 = {t11 (1), t12 (2); t22 (2); t31 (1), t32 (2); t41 (2), t42 (2); t51 (2), t52 (2)}; Continue selecting transitions from X1 and moving it to X2. Without loss of generalization, transition t22 whose mark is non-zero is chosen and moved to X2, so X2 = {t21, t22}. Update the mark of each transition in X1, so P1 = {t11 (1), t12 (1); t31 (1); t41 (2); t51 (2), t52 (2)}. Select transition t31whose mark is non-zero and move it to X2, so X2 = {t21, t22, t31}. Update the mark of each transition in X1, P1 = {t11 (1), t12 (1); t32 (1); t41 (1); t51 (2), t52 (2)}. Select transition t32 and move it to X2, so X2 = {t21, t22, t31, t32}. Update the mark of each transition in X1 again, P1 = {t11 (1), t12 (1); t31 (1), t32 (2); t41 (2), t42 (2); t51 (2), t52 (2)}, so X2 = {t21, t22; t31, t32; t41}. Update the mark of each transition in X1, P1={t11 (1), t12 (1); t42 (1); t51 (1), t52 (2)}. Select transition t42 and move it to X2 and X2 = {t21, t22; t31, t32; t41, t42}. Update the mark of each transition in X1, P1={t11 (1), t12 (1); t51 (1), t52 (1)}. Select transition t51 and move it to X2 and X2 = {t21, t22; t31, t32; t41, t42, t51}. Update the mark of each transition in X1 and P1 = {t11 (0), t12(1); t51(1)}. Select transition t52 and move it to t52 and X2 = {t21, t22; t31, t32; t41, t42; t51, t52}. Update the mark of each transition in X51, P1 ={t11 (0), t12 (0)} and the selecting and moving operations on P1 have been finished. Next, repeat the selecting and moving operations on X2. At last, we can get X1 = {t11, t12}; X2 = {t21, t22}; X3 = {t31, t32}; X4 = {t41, t42}; X5 ={ t51, t52}.
Step 6: To obtain connected subnets. Y1 = {t11, t12}; Y2 = {t21, t22}; Y3 = {t31, t32}; Y4 = {t41, t42}; X5 ={ t51, t52}.
Step 7: Output the outface subnet. Firstly, we output the outface subnet of Y1. For transition t11, if there is an edge which connects t11 and si, then there will be an edge connecting t11 and si. Repeat the processing on t12, then we get the subnet of Σ1. Using the same method, we can get the subnets of Σ1, Σ2, Σ3, Σ4 and Σ5.
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.
The output result of the whole algorithm is shown in Fig. 2.
In order to analyze properties of structure-complex Petri nets, the decomposition for a Petri net based on the indexes of transitions is a very convenient and useful approach. This study proposes a polynomial-time 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.
This study is supported partly by the NSFC under Grant No.60603090, 90718011 and 50875158; Science and Technology Development Fund of Shandong Province of China (2010GSF10811); the Excellent Young Scientist Foundation of Shandong Province of China under Grant No. BS2009DX004; the Special Fund for Fast Sharing of Science Study in Net Era by CSTD (20093718110008); the Open Project of Computer Architecture Lab of ICT, CAS, (No. ICT-ARCH200807); the Research Foundation of Qingdao under Grant No.10-3-3-32-nsh; Foundation for Distinguished Young Scholars of SDUST and the Taishan Scholar Program of Shandong Province.