**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.

PDF Abstract XML References Citation

**Received:**October 23, 2011;

**Accepted:**December 26, 2011;

**Published:**March 26, 2012

####
**How to cite this article**

*Information Technology Journal, 11: 768-774.*

**DOI:**10.3923/itj.2012.768.774

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

**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_{0}}, where N = {P, T; F} is a net and M_{0}: P→Z^{+} (Z^{+} is the non-negative integer set) is the initial state of Σ. A state M is reachable from M_{0} if there is a transition firing sequence σ such that M_{0} [σ>M. We use R(M_{0}) to represent the set of all reachable states from M_{0}. Let Σ = (P, T; F, M) be a Petri net. A 3-tuple RMG (Σ) = (R(M_{0}), E, f) is defined as the reachable marking graph, where: E = {(M_{i}, M_{j})|M_{i}, M_{j} ε R(M_{0}), ∃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_{0}) be a Petri net. A function f_{T}: T→ {1, 2, 3,..., k} is an index function of T, iff ∀t_{1}, t_{2}εT, if t^{•}_{1}∩t^{•}_{2} ≠ ø or f_{T}(t_{1}) ≠ f_{T}(t_{2}). f_{T}(t) is named as the index of the transition t.

**Definition 2 (Zeng, 2006):** Let Σ = (P, T; F, M_{0}) 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_{0}) 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_{0}) 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_{0}) 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_{0}) based on the index function of transitions and R (M_{0}) be the state set of Σ and R (M_{0i}) be the state set of Σ_{i}, respectively. A projection Γ_{P→Pi}: R (M_{0})→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_{0}) 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_{0}) 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_{1}) = f(t_{2}) = f(t_{4}) = 1; f(t_{3}) = f(t_{5}) = (t_{6}) = f(t_{7}) = 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 Σ_{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} = (P_{i}, T_{i}; F.M_{0i}) (iε {1, 2, 3... k}) be the decomposed net of Σ = (P_{i}, T_{i}; F.M_{0}) 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(M_{0}) = R(M_{0i}), (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 Σ_{1} and Σ_{2}, 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_{0}) 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_{0}) = 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_{0}) 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_{0}) 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_{0}) 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_{0}) 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_{0}) 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}), P_{1} = {p_{1}, p_{2}, p_{4}}, M_{0} = (1, 0, 0,), M_{1} = (0, 1, 0), and M_{2} = (0, 0, 1) |

• | In RMG(Σ_{2}), P_{2} = {p_{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}}, M_{0} = (1, 0, 0, 1, 0), M_{1} = (0, 1, 0, 0, 1), M_{2} = (0, 0, 1, 0, 1), M_{3} = (0, 1, 0, 1, 0), M_{4} = (1, 0, 0, 0, 1), M_{5} = (0, 0, 1, 0, 1) |

Since, P_{Δ} = {p_{1}, p_{4}}, the simplified reachable marking graphs corresponding to the decomposed subnets is given in Fig. 4, where:

• | In SRMG_{PΔ} (Σ_{1}), M_{0}^{i} = Γ_{Pi→PΔ} (M_{0}) = (1, 0), M’_{1} = Γ_{pi→PΔ }(M_{1}) = (0, 0), and M’_{2} = Γ_{pi→PΔ} (M_{2}) = (0, 1) |

• | In SRMG_{PΔ} (Σ_{2}), M’_{0} = Γ_{P2→PΔ} (M_{0}) = Γ_{P2→PΔ }(M_{4}) = (1, 0), M’_{1} = Γ_{P2→PΔ} (M_{1}) = Γ_{P2-PΔ} (M_{3}) = (0, 0), and M’_{2} = Γ_{P2→PΔ} (M2) = Γ_{P2→PΔ}(M_{5}) = (0, 1) |

From SRMG_{PΔ} (Σ_{1}) and SRMG_{PΔ} (Σ_{2}) in Figure 4, we can see:

Thus, RMG(Σ_{1}) and RMG(Σ_{2}) is isomorphic on P_{Δ} = {P_{1}, P_{4}}.

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.

**ACKNOWLEDGMENTS**

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).

####
**REFERENCES**

- Murata, T., 1989. Petri nets: Properties, analysis and applications. Proc. IEEE., 77: 541-580.

CrossRefDirect Link - Jiang, C., 1997. Petri net dynamic invariance. Sci. China, Series E: Technol., 40: 605-611.

Direct Link - Zeng, Q.T., 2004. Behavior descriptions of structure-complex Petri nets based on synchronous composition. J. Software, 15: 327-337.

Direct Link - Lee-Kwang, H., J. Favrel and P. Baptiste, 1987. Generalized Petri net reduction method. IEEE Trans. Syst. Man Cybernetics, 17: 297-303.

Direct Link - Suzuki, I. and T. Murata, 1983. A method for stepwise refinement and abstraction of Petri nets. J. Comput. Syst. Sci., 27: 51-76.

Direct Link - Zeng, Q., H. Wang, D. Xu, H. Duan and Y. Han, 2008. Conflict detection and resolution for workflow constrained by resources and non-determined duration. J. Syst. Software, 81: 1491-1504.

Direct Link - Wang, H. and Q. Zeng, 2008. Modeling and analysis for workflow constrained by resources and non-determined time: An approach based on petri nets. IEEE Trans. Syst. Man Cybernetics A, 38: 802-817.

CrossRef - Zeng, Q., 2007. Two symmetrical decomposition methods for structure-complex Petri net and their applications. ACIS Int. Conf. Software Engin. Artificial Intelli. Networking Parallel/Distributed Comput., 3: 1101-1106.

CrossRefDirect Link - Zeng, Q., X. Hu, J. Zhu and H. Duan, 2008. A polynomial-time decomposition algorithm for a petri net based on indexes of places. J. Applied Sci., 7: 4668-4673.

CrossRefDirect Link - Zeng, Q., 2011. A polynomial-time decomposition algorithm for petri nets based on indexes of transitions. Inform. Technol. J., 10: 856-862.

CrossRefDirect Link - Zeng, Q., 2008. A construction method for the process expression of petri net based on decomposition. Inform. Technol. J., 7: 420-429.

CrossRefDirect Link - Meng, D., Q. Zeng, F. Lu, J. Sun and J. An, 2011. Cross-Organization Task Coordination Patterns of Urban Emergency Response Systems. Inform. Technol. J., 10: 367-375.

CrossRefDirect Link - Du, Y.Y. and B.Q. Guo, 2009. Logic petri nets and equivalency. Inform. Technol. J., 8: 95-100.

CrossRefDirect Link - Liu, W. and Y. Du 2009. Modeling multimedia synchronization using petri nets. Inform. Technol. J., 8: 1054-1058.

CrossRefDirect Link - Liu, W., Y. Du and H. Sun, 2009. Soundness analysis of T-restricted interorganizational logical workflow nets. Inform. Technol. J., 8: 821-829.

CrossRefDirect Link - Cui, T., Q. Zeng and D. Zhang, 2011. Recognition algorithm design and complex analysis for languages of S-nets. Inform. Technol. J., 10: 106-112.

CrossRefDirect Link - Sun, S.X., Q. Zeng and H. Wang, 2011. Process-mining-based workflow model fragmentation for distributed execution. IEEE Trans. Syst. Man Cybern. Part A: Syst. Hum., 41: 294-310.

CrossRefDirect Link