Invariant Decomposition Conditions for Petri Nets Based on the Index of Transitions

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, M₀}, where N = {P, T; F} is a net and M₀: P→Z⁺ (Z⁺ is the non-negative integer set) is the initial state of Σ. A state M is reachable from M₀ if there is a transition firing sequence σ such that M₀ [σ>M. We use R(M₀) to represent the set of all reachable states from M₀. Let Σ = (P, T; F, M) be a Petri net. A 3-tuple RMG (Σ) = (R(M₀), E, f) is defined as the reachable marking graph, where: E = {(M_i, M_j)|M_i, M_j ε R(M₀), ∃t_k ε t, M_i [t_k>M_j}, f: E→T, f (M_i, M_j) = t_k, iff M_i [t_k>M_j, V is named as the place set of RMG (Σ), E is named as the arc set of RMG (Σ). If f (M_i, M_j), t_k is the side mark of f (M_i, M_j).

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, M₀) be a Petri net. A function f_T: T→ {1, 2, 3,..., k} is an index function of T, iff ∀t₁, t₂εT, if t^•₁∩t^•₂ ≠ ø or f_T(t₁) ≠ f_T(t₂). f_T(t) is named as the index of the transition t.

Definition 2 (Zeng, 2006): Let Σ = (P, T; F, M₀) be a Petri net and f_T: T→ {1, 2, 3,..., k} be the index function of T. Petri net Σ_i = (P_i, T_i; F.M_0i) (iε{1, 2, 3,..., k}) is a decomposed net of Σ based on f_T iff Σ_i satisfies the following conditions:

Definition 3 (Wu, 2006): A Petri net Σ = (P, T;F, M₀) is a T-Net iff ∀pεP such that |^•p|≤1 and |p^•|≤1.

Theorem 1 (Zeng, 2006): Let Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F, M₀) based on the function index of f_T 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 = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M₀) based on the function index of f_T iff:

Definition 4: Let Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M₀) based on the index function of transitions and R (M₀) be the state set of Σ and R (M_0i) be the state set of Σ_i, respectively. A projection Γ_P→Pi: R (M₀)→R(M_0i)(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 P_i. Γ_P→Pi is denoted as the projection function from R(M₀) to R(M_0i) and Γ_Pi→P is named as the inverse projection of Γ^¯1_P→Pi, (i = 1, 2, ...k).

Theorem 3: Let Σ_i = (P, T; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M₀) based on the index of transitions, such that:

A Petri net example is shown in Fig. 1. The index function f_T: T→{1, 2... k} is defined as: f(t₁) = f(t₂) = f(t₄) = 1; f(t₃) = f(t₅) = (t₆) = f(t₇) = 2

Obviously, f_T 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 Σ₁ and Σ₂, 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 = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P_i, T_i; F.M₀) 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_Δ = P_i∩P_j and P_i and P_j is the place set of Σ₁ and Σ₂, respectively.

Theorem 4: Let Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T; F.M₀) based on the index of transitions. For all i, jε{1, 2, 3... k}(i ≠ j), if P_Δ ≠ø such that P_Δ = P_i∩P_j, Γ_P→Pi R(M₀) = R(M_0i), (iε{1, 2, ... k}), iff ∀i, jε{1, 2, 3...k} (i ≠j), Γ_Pi→PΔ (R(M_0i)) = Γ_pj→PΔ (R(M_0j)).

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 = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M₀) based on the index of transitions.

Proof:

From Theorem 4 and 5, Corollary 1 can be obtained.

Corollary 1: Let Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M₀) 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(M_0i)) = Γ_Pj→PΔ(R(M_0j)).

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) = <V_i, E_i;f_i>(i = 1, 2, ...k) be the reachable marking graph of Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}), the subnets decomposed from Petri net Σ based on the index of transitions. SRMG_PΔ(Σ_i) = Γ_pi→PΔ (RMG(Σ_i)) is defined as the simplified reachable marking graph of RMG (Σ_i) based on the place set P_Δ, where SRMG_PΔ(Σ_i) = <V_iΔ, E_iΔ; f_iΔ>, 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) = <V_i, E_i;f_i>(i = 1, 2, ...k) be the reachable marking graph of Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) , the subnets decomposed from Petri net Σ based on the index of transitions and SRMG_PΔ(Σ_i) be the simplified reachable marking graph of RMG(Σ_i) based on the place set P_Δ, where, SRMG_PΔ(Σ_i) = <V_iΔ, E_iΔ; f_iΔ>. 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) = <V_i, E_i;f_i>(i = 1, 2, ...k) be the reachable marking graph of Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}), the subnets decomposed from Petri net Σ based on the index of transitions. If P_Δ ≠i, Γ_pi→PΔ (R (M_0i)) = Γ_Pj→PΔ (R (M_0j)) 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 = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M₀) based on the index of transitions and RMG(Σ_i) be the reachable marking graph of Σ_i Γ_pi→PΔ (R (M_0i)) = Γ_Pj→PΔ (R (M_0j)) iff Φ_PΔ (RMG(Σ_i)) ≅ Φ_PΔ (RMG(Σ_j)) for ∀i, jε{1, 2, 3...k} such that P_Δ ≠ ø.

Corollary 3: Let Σ_i = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M₀) based on the index of transitions and RMG(Σ_i) be the reachable marking graph of Σ_i Γ_pi→PΔ (R (M_0i)) = Γ_Pj→PΔ (R (M_0j)) 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 = (P_i, T_i; F.M_0i) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P, T, F, M₀) 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_Δ = {p₁, p₄}, 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 SRMG_PΔ (Σ₁) and SRMG_PΔ (Σ₂) in Figure 4, we can see:

Thus, RMG(Σ₁) and RMG(Σ₂) is isomorphic on P_Δ = {P₁, P₄}.

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.