Abstract: With the decomposition method of Petri net by assigning an index of the transition set, a structure-complex net system can be decomposed to a set of structure-simple subnets, named T-net. There is a projection relation of the reachable marking set and languages between the original net system and the subnet systems decomposed. However, some unnecessary states and languages are also added in the subnet systems. This study presents the deep research results on the decomposition method of Petri nets based on the index of transitions. A set of necessary and sufficient conditions for keeping the states and languages invariant between the original system and the subnet systems is obtained. Based on the simplified reachable marking graph, an algorithm is given to decide the states and languages invariant.
INTRODUCTION
As tools of modeling and analyzing physical systems, Petri nets have been widely applied in a large number of areas to model, analyze and manipulate real systems, which provides users with an integrated modeling, analyzing and manipulating environment, so as to give a reliable basis for the analyze of real system (Sun et al., 2011; Zeng et al., 2008a; Zeng and Duan, 2007; Wang and Zeng, 2008; Meng et al., 2011; Du and Guo, 2009; Liu and Du, 2009; Liu et al., 2009). The greatest obstacle to the application of Petri nets in real systems is the state space explosion, which arises while analyzing the structural properties of Petri nets. Because of the complexity of the real system, this problem has not been solved properly. To deal with the state space explosion of Petri nets, large numbers of researchers have done much work. They have presented the idea of Petri net reduction, Petri net operation, Petri net composition, stepwise refinement and so on (Jiang, 1997, 2000; Wang, 2001a, b; Jiang and Wu, 1992; Zeng, 2004; Lee-Kwang et al., 1987; Suzuki and Murata, 1983; Wang, 1999; Zeng and Wu, 2002, 2004). These works can be divided into two methods. One method is to compose structure-complex net system using a set of structure-simple nets so as to obtain the property of the complex system by analyzing the property of simple nets (Jiang, 1997, 2000; Wang, 2001a; Jiang and Wu, 1992; Zeng, 2004). The concept of synchronous composition of Petri nets and analyzes some conditions to keep states and behaviors invariant during the process of composition was given (Jiang, 1997, 2000). Wang (2001b) introduced a modeling method for FMS (Flexible Manufacture System) based on the synchronous composition of Petri net, with which divides physical objects into work type and resource type. Jiang and Wu (1992) defined an algebraic operation, named net operation and tried to build large net system via this algebraic operation. The structural properties during the process of net operations were also discussed (Jiang and Wu, 1992). Zeng (2004) extended the concept of synchronous composition to more than two Petri nets, which was used to express the language behavior of a structure-complex Petri net. Another method (Lee-Kwang et al., 1987; Suzuki and Murata, 1983) is to decompose a structure-complex net system to a series of structure-simple nets, hoping the original properties of the net can be reflected in the subnets. The method of the sum decomposition and the union decomposition were presented (Wang, 1999, 2001a). However, only the structural properties between the original net system and the subnets were discussed in details while the state and behavior relations, which are more widely used in the process of a real system, were not discussed (Wang, 1999, 2001b). To solve this problem, the decomposition method for petri nets by defining the index of places and transitions was given, respectively (Zeng, 2007, 2011; Zeng et al., 2008b) which can decompose a structure-complex Petri net into a set of S-nets (Zeng, 2011; Cui et al., 2011) or T-nets (Wu, 2006). A new decomposition method for Petri net by defining the index of places is given, with which the decomposed subnets are all S-nets (Zeng and Wu, 2002). They also give a deep research on this decomposition method and a necessary and sufficient condition for keeping the state and language invariant between the original system and the subnet system has been obtained (Zeng and Wu, 2004).In this study, we keep on the research of the decomposition method based on the index of transitions (Zeng, 2011, 2006), especially on the projection relation of the reachable marking sets and the languages between the original system and the subnet systems. A necessary and sufficient condition for keeping the states and languages invariant between the original system and the subnet system has been obtained. Based on the simplified reachable marking graph, an algorithm is given to decide the states and languages invariant.
BASIC CONCEPTS OF PETRI NETS
It is assumed that readers are familiar with the basic concepts of Petri nets (Wu, 2006; Zeng, 2008; Murata, 1989; Peterson, 1981). Some of the essential terminologies and notations about Petri nets used in this study are listed as follows:
A tuple N = {P, T; F} is named as a net iff :
| (1) |
| (2) |
| (3) |
where, Dom(F) = {x ε P∪T|∃y ε P∪T: (x, y)ε F} and Dom(F) = {x ε P∪T|∃y ε P∪T: (y, x) ε F}.
For all xεP∪T, the set •x = {y | y ε P∪T ∧ (y, x) ε F} is named as the pre-set of x and the set x• = {y | y ε P∪T∧(x, y) ε F} is named as the post-set of x.
A Petri net is a 4-tuple Σ = {P, T; F, M0}, where N = {P, T; F} is a net and M0: P→Z+ (Z+ is the non-negative integer set) is the initial state of Σ. A state M is reachable from M0 if there is a transition firing sequence σ such that M0 [σ>M. We use R(M0) to represent the set of all reachable states from M0. Let Σ = (P, T; F, M) be a Petri net. A 3-tuple RMG (Σ) = (R(M0), E, f) is defined as the reachable marking graph, where: E = {(Mi, Mj)|Mi, Mj ε R(M0), ∃tk ε t, Mi [tk>Mj}, f: E→T, f (Mi, Mj) = tk, iff Mi [tk>Mj, V is named as the place set of RMG (Σ), E is named as the arc set of RMG (Σ). If f (Mi, Mj), tk is the side mark of f (Mi, Mj).
DECOMPOSITION OF PETRI NET BASED ON THE INDEX OF TRANSITIONS
Here, we introduce the method to decompose a structure-complex Petri net based on an index function defined on the transition set (Zeng, 2007, 2011).With this method, a structure-complex Petri net can be decomposed into a set of structure-simple nets such that |p•|≤1 and |•p| ≤ 1 for all places.
Definition 1 (Zeng, 2006): Let Σ = (P, T; F, M0) be a Petri net. A function fT: T→ {1, 2, 3,..., k} is an index function of T, iff ∀t1, t2εT, if t•1∩t•2 ≠ ø or fT(t1) ≠ fT(t2). fT(t) is named as the index of the transition t.
Definition 2 (Zeng, 2006): Let Σ = (P, T; F, M0) be a Petri net and fT: T→ {1, 2, 3,..., k} be the index function of T. Petri net Σi = (Pi, Ti; F.M0i) (iε{1, 2, 3,..., k}) is a decomposed net of Σ based on fT iff Σi satisfies the following conditions:
Definition 3 (Wu, 2006): A Petri net Σ = (P, T;F, M0) is a T-Net iff ∀pεP such that |•p|≤1 and |p•|≤1.
Theorem 1 (Zeng, 2006): Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F, M0) based on the function index of fT iff:
For all k>1, if ∀iε{1, 2, 3... k},∃j{1, 2, 3...k}, i ≠ j, then,
Theorem 1 indicates that a Petri net can be decomposed into a set of structure-simple subnets, named T-Nets. A Polynomial-time Decomposition Algorithm was given (Zeng, 2011).
| Fig. 1: | A Petri net example |
| Fig. 2: | Two decomposed subnets |
Theorem 2 (Zeng, 2006): Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M0) based on the function index of fT iff:
Definition 4: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M0) based on the index function of transitions and R (M0) be the state set of Σ and R (M0i) be the state set of Σi, respectively. A projection ΓP→Pi: R (M0)→R(M0i)(i = 1, 2, ... k) such that ΓP→Pi (M) is the states which are obtained from M by deleting all the places that do not belong to Pi. ΓP→Pi is denoted as the projection function from R(M0) to R(M0i) and ΓPi→P is named as the inverse projection of Γ¯1P→Pi, (i = 1, 2, ...k).
Theorem 3: Let Σi = (P, T; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M0) based on the index of transitions, such that:
A Petri net example is shown in Fig. 1. The index function fT: T→{1, 2... k} is defined as: f(t1) = f(t2) = f(t4) = 1; f(t3) = f(t5) = (t6) = f(t7) = 2
Obviously, fT satisfies Definition 2. Using the decomposition method based on the index of transitions, the Petri net shown in Fig. 1 can be divided into two subnets Σ1 and Σ2, which are illustrated in Fig. 2.
NECESSARY AND SUFFICIENT DECOMPOSITION CONDITIONS FOR KEEPING THE PROPERTY INVARIANT
It can be known from Theorem 3 that the projection of the original net system on the subnet systems is only a subset of the subnet’s states and behaviors. The subnets add some unnecessary states and behaviors while keeping the properties of the original Petri net. Here, we present the necessary and sufficient conditions for keeping the property invariant while the decomposition.
Firstly, the definition of the property invariance while the decomposition is given.
Definition 5: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (Pi, Ti; F.M0) based on the index of transitions, If:
| (1) |
ΓT→Ti (L(Σ)) = L(Σi) (iε{1, 2, 3... k}) , then the decomposed subnets keep the behavior property of the original net |
| (2) | ΓP→Pi R(M0) = R(M0i), (iε{1, 2, ... k}), then the decomposed subnets keep the state property of the original net |
If (1) and (2) are satisfied together, the decomposed subnets keep the property invariant of the original net.
From the second conclusion of Theorem 1, we know that if there are more than one decomposed subnets, for any Σi, there necessarily exists another subnet Σj (i ≠ j), such that PΔ ≠ø, where PΔ = Pi∩Pj and Pi and Pj is the place set of Σ1 and Σ2, respectively.
Theorem 4: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M0) based on the index of transitions. For all i, jε{1, 2, 3... k}(i ≠ j), if PΔ ≠ø such that PΔ = Pi∩Pj, ΓP→Pi R(M0) = R(M0i), (iε{1, 2, ... k}), iff ∀i, jε{1, 2, 3...k} (i ≠j), ΓPi→PΔ (R(M0i)) = Γpj→PΔ (R(M0j)).
| Proof: |
Theorem 4 shows that in order to keep the state property of the decomposed subnets during the decomposition based on the index of transitions, the projection of subnets on the public intersection must be equal with each other, vice versa. Theorem 5 presents the conditions to keep the behavior property during the process of decomposition.
Theorem 5: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M0) based on the index of transitions.
| Proof: |
From Theorem 4 and 5, Corollary 1 can be obtained.
Corollary 1: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M0) based on the index of transitions, ∀i, jε{1, 2, 3, ...k}, (i ≠j), if PΔ ≠ø, ΓT→Ti (L(Σ)) = L (Σi) iff ΓPi→PΔ(R(M0i)) = ΓPj→PΔ(R(M0j)).
A DECISION ALGORITHM FOR DECOMPOSITION PROPERTY INVARIANCE
Here, we have presented the sufficient and necessary conditions for keeping the state and behavior property during the process of decomposition. Here, an algorithm to decide the property invariant is given based on the simplified reachable marking graph.
Definition 6: Let RMG(Σi) = <Vi, Ei;fi>(i = 1, 2, ...k) be the reachable marking graph of Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}), the subnets decomposed from Petri net Σ based on the index of transitions. SRMGPΔ(Σi) = Γpi→PΔ (RMG(Σi)) is defined as the simplified reachable marking graph of RMG (Σi) based on the place set PΔ, where SRMGPΔ(Σi) = <ViΔ, EiΔ; fiΔ>, if the following conditions are satisfied:
Definition 7 given a formal definition of isomorphism between two reachable marking graphs of Petri nets based on the public place set PΔ ≠ ø.
Definition 7: Let RMG(Σi) = <Vi, Ei;fi>(i = 1, 2, ...k) be the reachable marking graph of Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) , the subnets decomposed from Petri net Σ based on the index of transitions and SRMGPΔ(Σi) be the simplified reachable marking graph of RMG(Σi) based on the place set PΔ, where, SRMGPΔ(Σi) = <ViΔ, EiΔ; fiΔ>. RMG (Σi) and RMG (Σj) is isomorphic on PΔ iff:
Denote ΦPΔ (RMG(Σi)) ≅ ΦPΔ RMG(Σj) if RMG(Σi) and RMG(Σj) are isomorphic on PΔ.
Theorem 6: Let RMG(Σi) = <Vi, Ei;fi>(i = 1, 2, ...k) be the reachable marking graph of Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}), the subnets decomposed from Petri net Σ based on the index of transitions. If PΔ ≠i, Γpi→PΔ (R (M0i)) = ΓPj→PΔ (R (M0j)) iff ΦPΔ ((RMG(Σi)) ≅ ΦPΔ (RMG(Σj)).
Proof: The conclusion can be easily obtained based on Definition 6 and 7, and Theorem 5 and 6.
Based on the Theorem 5 and 6, Corollary 2 and 3 can be obtained.
Corollary 2: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M0) based on the index of transitions and RMG(Σi) be the reachable marking graph of Σi Γpi→PΔ (R (M0i)) = ΓPj→PΔ (R (M0j)) iff ΦPΔ (RMG(Σi)) ≅ ΦPΔ (RMG(Σj)) for ∀i, jε{1, 2, 3...k} such that PΔ ≠ ø.
Corollary 3: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M0) based on the index of transitions and RMG(Σi) be the reachable marking graph of Σi Γpi→PΔ (R (M0i)) = ΓPj→PΔ (R (M0j)) iff ΦPΔ (RMG(Σi)) ≅ ΦPΔ (RMG(Σj)) for ∀i, jε{1, 2, 3...k} such that PΔ ≠ ø.
According to Corollary 2 and 3, Algorithm 1 presents an algorithm to decide the property invariant of the decomposed subnets based on the simplified reachable marking graph.
Algorithm 1: Let Σi = (Pi, Ti; F.M0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M0) based on the index of transitions and RMG(Σi) be the reachable marking graph of Σi.
AN EXAMPLE
Here, the example shown in Fig. 1 is used to verify the decision algorithm shown in Algorithm 1. The reachable marking graphs of the decomposed subnets are shown in Fig. 3, respectively.
| • | In RMG(Σ1), P1 = {p1, p2, p4}, M0 = (1, 0, 0,), M1 = (0, 1, 0), and M2 = (0, 0, 1) |
| • | In RMG(Σ2), P2 = {p1, p2, p3, p4, p5, p6}, M0 = (1, 0, 0, 1, 0), M1 = (0, 1, 0, 0, 1), M2 = (0, 0, 1, 0, 1), M3 = (0, 1, 0, 1, 0), M4 = (1, 0, 0, 0, 1), M5 = (0, 0, 1, 0, 1) |
Since, PΔ = {p1, p4}, the simplified reachable marking graphs corresponding to the decomposed subnets is given in Fig. 4, where:
| • | In SRMGPΔ (Σ1), M0i = ΓPi→PΔ (M0) = (1, 0), M’1 = Γpi→PΔ (M1) = (0, 0), and M’2 = Γpi→PΔ (M2) = (0, 1) |
| • | In SRMGPΔ (Σ2), M’0 = ΓP2→PΔ (M0) = ΓP2→PΔ (M4) = (1, 0), M’1 = ΓP2→PΔ (M1) = ΓP2-PΔ (M3) = (0, 0), and M’2 = ΓP2→PΔ (M2) = ΓP2→PΔ(M5) = (0, 1) |
From SRMGPΔ (Σ1) and SRMGPΔ (Σ2) in Figure 4, we can see:
Thus, RMG(Σ1) and RMG(Σ2) is isomorphic on PΔ = {P1, P4}.
| Fig. 3: | The reachable marking graphs of the decomposed subnets |
| Fig. 4: | The simplified reachable marking graphs |
It indicates that the decomposed subnets keep the state and the behavior property of the original Petri net.
CONCLUSIONS
In order to analyze properties of structure-complex Petri nets, the decomposition based on the index of transitions is a very convenient and useful approach. With this decomposition method, a structure-complex net system is decomposed to a set of structure-simple subnets, named T-Nets. There is a projection relation of the reachable marking sets and languages between the original net system and the subnet systems. However, some unnecessary states and languages are also added in the subnet systems. This study presents the deep research results on the decomposition method of Petri nets based on the index of transitions. The necessary and sufficient conditions for keeping the property invariant between the original system and the subnet systems are obtained. At the same time, a decision algorithm for the property invariant decomposition of Petri net based on the simplified reachable marking graph has been presented. The conclusions and algorithms proposed in this paper have contributions for Petri nets used to model and analyze many real physical systems.
ACKNOWLEDGEMENTS
This study is supported partly by the NSFC (61170079) and National Sci. and Tech. Support Program (2009BAG13A02) of China; Sci. and Tech. Development Fund of Shandong Province of China (2010GSF10811); Specialized Research Fund for the Doctoral Program of Higher Education of China (20103718110007), Sci. and Tech. Development Fund of Qingdao(10-3-3-32-nsh), Excellent Young Scientist Foundation of Shandong Province (BS2009DX004, BS2010DX009 and 2010KYJQ101); and Foundation for Distinguished Young Scholars of SDUST (JQ200816).