ABSTRACT
Process expression is one of the most useful tools to describe the process semantics of a Petri net. However, it is usually not easy to obtain the process expression of a Petri net directly. In this research, a construction method is proposed to obtain the process expressions of all kinds of Petri nets based on decomposition. With this decomposition method, a Petri net is decomposed into a set of SNets. The process properties of the decomposition nets are easy to analyze since they are wellformed and their process expressions are easier to obtain. With the process expressions of the decomposition nets, an algorithm to obtain the process expression of the original Petri net is presented, which is expressed by the synchronization shuffle operation between processes.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/itj.2008.420.429
URL: https://scialert.net/abstract/?doi=itj.2008.420.429
INTRODUCTION
To use Petri net for analyzing the properties of the physical systems, several methods have been presented in the net theory, among which process is a powerful tool for describing dynamical behaviors of net systems. Petri net processes are very convenient for analyzing concurrent phenomena and system properties relating to concurrency. This is an advantage of process method compared to other analysis methods about Petri net (Yuan, 2005; Garg and Ragunath, 1992; Murata, 1989). However, a process of a Petri net only gives one possible running case for the net system. There are usually many (sometimes maybe infinite) cases during a Petri net system running. It is difficult to obtain all the running cases, which brings difficulties for the analysis of Petri nets using their processes. Lu (1992a, b) has developed a new kind of nets, P/R nets, as a substitute for occurrence nets to describe executions of elementary net systems. A P/R net consists of a family of occurrences nets (called pages by Lu) and a contact situation of elementary net system is resolved by using several pages. Zeng and Wu (2002c) introduce the concept of process net system of a Petri net. The process net system is a reconstruction Petri net based on the set of the basic process sections, which describes the process behaviors of the original system very well. Wu (1996) and Wu et al. (2000) present the concept of process expression for bounded Petri net and unbounded fair Petri net. Roughly, any process of a bounded Petri net or unbounded fair Petri net is really a composition of several basic process sections (called subprocess by Wu). Zeng and Wu (2003) have proved the onetoone corresponding relation between the transition firing sequences of the process net system and the processes of the original Petri net and presented a method to obtain the process expression of any unbounded Petri net based on its process net system.
This study proposes a new method to construct the process expression of a Petri net based on a kind of decomposition methods. This decomposition method is very useful for property analysis of structurecomplex Petri nets since the structure of the decomposition net is wellformed (Zeng and Wu, 2002a, 2004a, b). We analyze the language relations during the decomposition and present a method to obtain the language of a Petri net (Zeng and Wu, 2004a). In Zeng and Wu (2004b), we discuss the conditions to keep states and behaviors invariant during the decomposition and present the judgment algorithm. In this study, we analyze the process properties of the decomposition nets and present the methods to obtain their process expressions. By discussing the process relations during the decomposition, an algorithm is proposed to present the process expression of the original Petri net based on the process expressions of the decomposition nets. This method suits obtaining the process expression for bounded or unbounded, fair or unfair Petri nets and it is not necessary to construct the process net system.
RELATED TERMINOLOGY AND NOTATIONS ABOUT PETRI NET PROCESS
To save space, it is assumed that the readers are familiar with the basic definitions of Petri nets (Yuan, 2005; Murata, 1989; Zeng and Wu, 2002c; Wu, 1996). Some of the essential terminology and notations related to this research are defined as follows. Convenient to define, we only consider the process of P/T system and suppose that K = ω and W = 1. We also assume that the Petri net discussed in this work is finite and connected and is not an SNet (Yuan, 2005).
PROCESS AND BASIC PROCESS SECTION PETRI NET
Definition 1: A net N = (B, E; G) is an occurrence net if
(1)  ∀b ε B: ^{•}b≤1∧b^{•} ≤1 and 
(2)  ∀x, y ε B• E: (x, y) ε G^{+} →(y, x) ⊕ G^{+}, 
where, G^{+} is the transitive closure of the flow relation G.
Definition 2: Let N_{1} = (S, T; F) be a net and N_{2} = (B, E; G) be an occurrence net. A mapping Φn: B • E→S • T is a mapping from N_{2} to N_{1}, denoted by Φn: N_{2}→N_{1}, if it satisfies:
(1)  Φn(B) ⊆ S; Φn(E) ⊆ T, 
(2)  ∀x, yε B • E: (x, y)ε G 
(3)  ∀e ∈ E: Φn(^{•}e) = ^{•}Φn(e), Φn (e ^{•}) = Φn (e)^{•} 
Definition 3: Let Σ = (N_{1}, M_{0}) = (S, T; F, M_{0}) be a Petri net and N = (B, E; G) be a occurrence net. A process of Σ is a couple (N, Φn), where Φn is a mapping from N to N_{1} and satisfies the following conditions:
(1)  ∀b_{1}, b_{2}εB:(b_{1}≠b_{2}): Φn(b_{1}) = Φn(b_{2})→^{•}b_{1}≠^{C}b_{2} ∧b_{1}^{•}…b_{2}^{•} and 
(2)  ∀s ε S:{b Φn(b) = sΛ ^{•}b = φ} ≤M_{0} (s) 
Definition 4: Let Φn be a mapping from a occurrence net N = (B, E; G) to a Petri net Σ = (S, T; F, M). If:
(1) 
(2)  {b Φn(b) = sΛ ^{•}b = φ} =M_{0} (s) 
then P = (N, Φn) is said to be a surjective process of Σ.
Definition 5: Let P = (N, Φn) be a surjective process of Σ, where N = (B, E; G). Let u_{1} and u_{2} be two Scuts of N such that u_{1}≤u_{2}. We define N_{1} = (B_{1},E_{1}; G_{1}) such that:
(1)  B_{1}={x εB∃b_{1}εu_{1}, b_{2}εu_{2}: (b_{1}, x) εG*Λ(x, b_{2})εG*}; 
(2)  E_{1}={y εE∃b_{1}εu_{1}, b_{2}εu_{2}: (b_{1}, y) εG*Λ(y, b_{2})εG*}; 
(3)  G_{1} = G∩ ({B_{1}xE_{1}} •{E_{1}xB_{1}}) 
If Φn_{1}: N_{1}→Σ satisfies ∀xε B_{1}•E_{1}: Φn_{1}(x) = Φn(x), (N, Φn_{1}) is said to be a section (between u_{1} and u_{2}) of process P, sometimes it is also called a process section of Σ, denoted by (N[u_{1}, u_{2}], Φn) (Zeng and Wu, 2002c).
Definition 6: Let P = (N, Φn) be a surjective process of Σ and P_{1} = (N[u_{1}, u_{2}], Φn) be a process section of Σ. If any two scuts u_{i} and u_{j} (i, j≠1,2) in N[u_{1}, u_{2}] satisfies:
then P_{1} = (N[u_{1}, u_{2}], Φn) is said to be a basic process section of Σ.
The set of all the basic process sections of a Petri net Σ is denoted by BP(Σ) (Zeng and Wu, 2003).
PROCESS NET SYSTEM OF PETRI NET
The concept of process net system of a Petri net was first introduced by Zeng and Wu (2002c). The process net system Σ_{p} of a Petri net Σ describes the process behaviors of Σ very well. Every transition firing sequence of Σ_{p} is corresponding to a surjective process of Σ. If the last process section of a given surjective process is complete, there is a transition firing sequence corresponding to it.
Definition 7: Let P = ([u_{1}, u_{2}], Φn) be a basic process section of a Petri net Σ = (S, T; F, M_{0}) and Φn be the mapping from the occurrence net N = (B, E; G) to Σ.
(1)The sets ^{ 0}P = {ssεSΛΦn^{1 } (s)εu_{1}} and
P^{0} = {ssεSΛΦn^{1}(s)εu_{2}} are respectively named as the input and the output place set of P.
(2)The bag B(^{0}P) = {ssεSΛΦn^{1} (s)εu_{1}} is the input place bag of P, where
Similarly, the bag B(P^{0}) = {ssεSΛΦn^{1} (s)εu_{2}} is the output bag of P, where
Definition 8:^{ }Let BP(Σ) be the set of the basic process sections of Σ and S(P)⊆BP(Σ). We define
(1) 
(2) 
Definition 9: Let Σ = (S, T; F, M_{0}) be a Petri net. ∀Mε R(M_{0}), S_{1}⊆S, the projection of M on S_{1} (denoted by is defined by for all sεS_{1}.
Definition 10: Let Φn be a mapping from the occurrence net N = (B, E; G) to the Petri net Σ = (S, T; F; M_{0}) and BP (Σ) be the set of the basic process sections. Petri net Σ_{p} = (S_{p}, T_{p}; F_{p}, M_{0p}) is defined as the process net system of Σ iff
(1) 
(2)  There is a onetoone mapping ξ: T_{P}→BP(Σ) such that ∀tεT_{P}, ξ (t)εBP(Σ); 
(3) 
(4)  M_{op} = Γ_{S→Sp} (M_{0}) 
ROCESS EXPRESSION OF PETRI NET
The process expressions of a bounded Petri net and unbounded fair Petri net are defined in Wu (1996) and Wu et al. (2000), respectively. The following definition for process expression of a Petri net is an extension of the cases in Wu (1996) and Wu et al. (2000).
Definition 11: Let BP(Σ) be the set of the basic process sections of a Petri net Σ = (S, T; F, M_{0}), Exp (P(Σ)) be an expression whose alphabet is isomorphic to BP(Σ) and CRE (P(Σ)) be the set expressed by Exp (P(Σ)). Exp (P(Σ)) is defined as the process expression of Σ, if each surjective process of Σ is an element of the set
DECOMPOSITION BASED ON THE INDEX OF PLACE
Here, we introduce the decomposition method for a structurecomplex Petri net based on the indexes of places (Zeng and Wu, 2002a, 2004a, b).
Definition 12: Let Σ = (S, T; F, M_{0}) be a Petri net, a function f: S→{1, 2, …k} is said to be an index function defined on the place set if ∀ s_{1}, s_{2}εS,
f (s) is named as the index of place s (Zeng and Wu, 2002a).
Definition 13: Let Σ = (S, T; F, M_{0}) be a Petri net, f: S→{1, 2, …, k} be the index function on the places of Σ. Petri net Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (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 and Wu, 2002a).
Simply, Σ_{i} is said as the index decomposition net of Σ.
More discussions about this decomposition method can be found in Zeng and Wu (2002a, 2004a) and an algorithm of decomposition for a structurecomplex Petri net is also given in Zeng and Wu (2004a). The decomposition results with the method in definition 13 are usually not unique. With the results discussed in Zeng and Wu (2002a, 2004a), it is usually to take the case that k is with the minimal value as the best result.
Definition 14: A Petri net Σ = (S, T; F, M_{0}) is an SNet if ∀tεT:^{•}t≤1 and t ^{•}≤1 (Yuan, 2005).
Theorem 1: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2, …,k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}), then Σ_{i} is an Snet (Zeng and Wu, 2002a).
Accroding to Theorem 1, each of the index decomposition nets is wellformed and it is easier to analyze the properties of the index decomposition nets than the original Petri net. This is one of the main reasons to decompose a structurecomplex Petri net using this decomposition method.
Example 1: A Petri net Σ is shown in Fig. 1. We use the decomposition method in Definition 12 to decompose Σ.
A function f is first defined on the place set such that f(s_{1}) = f (s_{6}) = 1, f(s_{2}) = f(s_{3}) = 2, f(s_{4}) = f(s_{5}) = f (s_{7}) = 3.
Fig. 1:  A Petri net Σ 
Fig. 2:  Three SNets of Petri net Σ 
It can prove that f satisfies all the conditions in Definition 11. Based on the method of Definition 13, three index decomposition net systems Σ_{1}, Σ_{2} and Σ_{3} are obtained and shown in Fig. 2. Obviously,Σ_{1}, Σ_{2} and Σ_{3} are SNets.
PROCESS EXPRESSIONS OF THE DECOMPOSITION NET SYSTEMS
According to Theorem 1, each index decomposition net system is an SNet. We have analyzed the language and liveness characteristics of an SNet, respectively in Zeng and Wu (2002b) and Duan and Zeng (2004). Here, we analyze the process characteristics of an SNet (an index decomposition net system) and present the method to obtain its process expression so as to construct the process expression of the original Petri net.
The following two propositions can be obtained easily following the related definitions.
Proposition 1: Let P = (N, Φn) be a surjective process of an SNet Σ, where N = (B, E; G). For any e εE, ^{•}e≤1 and e^{•}≤1.
Proposition 2: Let Σ_{P} = (S_{P}, T_{P}; F_{P}, M_{0P}) be the process net system of an SNet Σ = (S, T; F, M_{0}). Σ_{P} is also an SNet.
Definition 15: Let Σ = (S, T; F, M_{0}) be an SNet. ∀tεT, t is a primitive transition of Σ if ^{•}t = 0 and t is a goal transition of Σ if t ^{•} = 0.In the index decomposition net, it is possible that there are primitive transitions or goal transitions. It is easy to transform an SNet with goal transitions into one SNet without goal transitions. The method is to add an output place for each goal transition in the original SNet. If we delete all the added places from all the processes of the new SNet without goal transitions, it can keep all states and behaviors of the original SNet invariant. Thus, the process semantics can be regarded as equal between the original SNet and the new SNet without goal transitions. Therefore, it is assumed that for each transition t in the index decomposition net discussed in this research satisfies ^{•} t≤1 and t ^{•} = 1.
All the SNets without goal transitions can be classified into four classes based on the standards of primitive transitions and initial markings. These four kinds of SNets, respectively are:
CSNets without primitive transitions and with empty markings. This kind of SNets has no any process, so it is not necessary to discuss.
CSNets without primitive transitions but with initial markings. It is obvious that this kind of SNets is Sgraph (state machine). Without interpretations, this kind of SNets is named as Sgraph directly in the following discussions.CSNets with primitive transitions but with empty initial markings. Without interpretations, this kind of SNets is named as SNet with Empty Markings directly in the following discussions.
CSNets with primitive transitions and with initial markings. Without interpretations, this kind of SNets is named as SNet with Initial Markings directly in the following discussions.
Next, we will discuss the process characteristics of each kind of the SNets based on the classification and present the method to obtain their process expression.
PROCESS EXPRESSION OF SGRAPH
Lemma 1: Each SGraph is bounded (Yuan, 2005).
Lemma 2: The process expression of each SGraph is a regular expression.
Proof: With the conclusions in Wu (1996), the process expression of a bounded Petri net is a regular expression.
Theorem 2: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2, …,k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}). Exp (P(Σ_{i})) is a regular expression if Σ_{i} is an SGraph.Example 2: Σ_{3} shown in Fig. 2c is an SNet. Based on its reachability graph, we can obtain the set of the basic process sections of Σ_{3}. The method to obtain the basic process sections can be seen in Wu (1996). BP(Σ_{3}) = {P_{31}}and P_{31} is shown in Fig. 3. In the process section, we directly use the names of place and transition to label the corresponding elements and the same to the following discussions. The process expression of Σ_{3} is Exp (P(Σ_{3})) = P_{31}*. It can be shown that each surjective process of Σ_{3} is the prefix of the language of Exp (P(Σ_{3})) = P_{31}*.
Fig. 3:  The basic process section of Σ_{3} 
PROCESS EXPRESSION OF SNET WITH EMPTY MARKINGS
Lemma 3: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε {1, 2, …, k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}). If there is one and only one primitive transition t`εT_{i} and ∀sεS: M_{0 }(s) = 0 in Σ_{i}, Σ_{i} has one and only one basic source process section.
Proof: Obviously.
Lemma 4: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε {1, 2, …, k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}). If there is one and only one primitive transition t`εT_{i} and ∀sεS: M_{0 }(s) = 0 in Σ_{i}, there is a regular expression RE such that Exp (P(Σ_{3})) = (RE)^{α}, where (RE)^{α} is the αclosure of RE.
Proof: Suppose that BP(Σ_{i}) is the set of the basic process sections of Σ_{i}. For any basic process in BP(Σ_{i}), it is denoted by P_{j} = (N[u_{1j}, u_{2j}], Φn) where 1≤j≤BP(Σ_{i}) and u_{1j} and u_{2j} are the first and last SCut of P_{j}. Based on BP(Σ_{i}), the process net system Σ_{i} = (S_{iP}, T_{iP}; F_{iP}, M_{0iP}) of Σ_{i} can be constructed, where
(1)  
(2)  T_{iP} = BP (Σ_{i}) and 
(3)  F_{iP} = {(u_{1j,} P_{j})(P_{j} εBP(Σ_{i})}•{(P_{j}, u_{2j}) P_{j} εBP(Σ_{i})}, where P_{1} = (N[u_{11}, u_{21}], Φn) is the source process section of Σ and u_{11} = φ. So, (u_{11}, P_{1}) ⊕ F_{P} . and 
(4)  ∀sεS_{P}: M_{0P} (s) = 0. 
According to Lemma 1 and 2, Σ_{iP} is an SNet with one and only one primitive transition and with empty markings, so L (Σ_{iP}) can be expressed by the αclosure of a regular expression. The proof can be seen in Zeng and Wu (2002b). With the definition of process net system, there is a onetoone corresponding relation between Exp (P(Σ_{i})) and L (Σ_{iP}). So, there is a regular expression RE such that Exp (P(Σ_{i})) = (RE)^{α}, where (RE)^{α} is the α closure of RE.
Example 3: An SNet Σ_{11} with one and only one primitive transition and has empty initial markings is shown in Fig. 4a and its two basic process sections are shown in Fig. 4b.
Fig. 4:  An SNet Σ_{11} and its two basic precess sections 
The process expression of Σ_{11} is Exp (P(Σ_{11})) = (P_{111} P_{112})^{α}, which can be obtained based on the process net system of Σ_{11}. It can be shown that each surjective process of Σ_{11} is the prefix of the language of Exp (P(Σ_{11})) = (P_{111}Ο P_{112})^{α}, where Ο is the connection operation between the basic process sections. The definitions and more discussions about operations between the basic process sections can be seen in Wu (1996).
Theorem 3: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2,…,k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{o}). If there are primitive transitions t_{1}, …, t_{n} (n≥2) and ∀sεS_{i} M_{0} (s) = 0 in Σ_{i}, there are regular expressions RE_{1}, …, RE_{n} such that Exp (P(Σ_{i})) = (RE_{1})^{α}… (RE_{n})^{α}.
Proof: Let T_{0} = {t_{1}, …, t_{n}}. To construct SNets Σ_{ij} = (S_{i}, T_{ij}; F_{ij}, M_{0i}) (jε{1, 2, …, n}) to prove the conclusion, where the place set S_{i} and initial marking M_{0i} keep invariant from Σ_{i} = (S_{i}, T_{i}; F_{j}, M_{0i}). Σ_{ij} = (S_{i}, T_{ij}; F_{ij}, M_{0i}) (jε{1, 2, …, n}) satisfies the following conditions,
(1) T_{ij} = (T_{i}T_{o}) U {t_{ij}}and
(2) F_{ij} = F_{i}(T_{0}{t_{ij}})xS_{i}
It is easy to prove Exp (P(Σ_{i})) = Exp (P(Σ_{i1}))… Exp (Σ_{in})).
For each Σ_{ij} = (S_{i}, T_{ij}; F_{ij}, M_{0i}) (j ε {1, 2, …, n}), there is one and only one primitive transition and with empty initial markings. With Lemma 4, there is a regular expression RE_{j} such that Exp (P(Σ_{i})) = (RE_{j})^{α}.
So, there are regular expressions RE_{1}, …, RE_{n} such that Exp (P(Σ_{i})) = (RE_{1})^{α} … (RE_{n})^{α}.
PROCESS EXPRESSION OF SNET WITH INITIAL MARKINGS
Theorem 4: Let Σ_{i} = (P_{i}, T_{i}; F_{i}, M_{0i}) (i ε {1, 2, …, k}), be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}). If there are primitive transitions t_{1}, …, t_{n} (n≥1 and {t_{1}, …, t_{n}}⊆T_{i}) and at least one place s ε S such that M_{0i} (s) ≠ 0 in Σ_{i}, there are regular expressions RE_{1},… , RE_{n} and RE_{n+1} such that Exp (P(Σ_{i})) = (RE_{1})^{α} … (RE_{n})^{α} RE_{n+1}.
Fig. 5:  The basic process section of Σ_{12} 
Proof: Let T_{0} = {t_{1}, …, t_{n}}. To construct two SNets Σ_{ij} = (S_{ij}, T_{ij}; F_{ij}, M_{0ij}) (j ε {1, 2} to prove the conclusion, where,
(1) S_{i1} = S_{i}, T_{i1} = T_{i}, F_{i1} = F_{i}, ∀s ε S_{i1}: M_{0il} (s) = 0 and
It is easy to prove Exp (P(Σ_{i})) = Exp (P(Σ_{i1})) Exp (P(Σ_{i2})) and Σ_{i1} satisfies all the conditions in Theorem 3 and Σ_{i2} is an Sgraph. With Theorem 3, there are regular expressions RE_{1}, …, RE_{n} such that Exp (P(Σ_{i1})) = (RE_{1})^{α} …(RE_{n})^{α}. With Theorem 1, Exp (Σ_{i2}) is a regular expression. So, there are regular expressions RE_{1}, …, RE_{n} and RE_{n+1} such that Exp (P(Σ_{i}) = (RE_{1})^{α} …(RE_{n})^{α} RE_{n+1}.
Example 4: We take the index decomposition net Σ_{1} shown in Fig. 2a as an example. Two new SNets Σ_{11} and Σ_{12} are constructed and shown in Fig. 5a and b, respectively. Σ_{11} is the SNet shown in Fig. 4, so Exp (P(Σ_{11})) = (P_{111}Ο P_{112})^{α}. Σ_{12} is an Sgraph and Exp (P(Σ_{12})) = P_{113}*, where the basic process section P_{113} is shown in Fig. 6. So, the process expression of Σ_{1} is Exp (P(Σ_{1})) = Exp (P(Σ_{11}))  Exp (P(Σ_{12})) = (P_{111}Ο P_{112})^{α}  P_{113}*.
PROJECTION AND SYNCHRONIZATION SHUFFLE OF PROCESSES
In order to analyze the process characteristics during the decomposition, the projection and synchronization shuffle operations of processes are defined in this section. Convenient to define, some notations are introduced first.
Let X be an alphabet. For any character αεX and any word ωεX*, # (α, ω) is the number of α occurring in ω.
Fig. 6:  The basic process section of Σ_{12} 
For any language L⊆X*, δ(L) = {xεX∃ωεL:#(x, ω)>0}. For example, δ(a+ab) = δ(aa+abbbb) = {a, b}. Obviously, δ(L)⊆X.
Definition 16: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2,…, k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}) and SN(*) be the set of occurrence net, where *ε{Σ, Σ_{1}, …, Σ_{k}}. For ∀NεSN(Σ), if Π: Φn(SN(Σ))_{i} (SN(Σ_{i})) satisfies the following conditions,
(1)∀bεB, to delete b and its input and output arcs if Φn(b)εS_{j} and j≠i and
(2)∀eεE, to delete e and its input and output arcs if Φn(e)εE_{j}E_{i} and j≠i,
Π is the projection from Φn(SN(Σ)) to Φn_{i}(SN(Σ_{i})) and denoted by .
For any basic process section, it is one part of the occurrence net of a Petri net. If SN(*) in Definition 16 is extended to contain all the basic process sections and other conditions are invariant, the projection of basic process section can be also obtained.
Definition 17: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2}) be two Petri nets and Exp (P(Σ_{i})) be the process expression of Σ_{i}. Exp (P(Σ_{1}))ΘExp (P(Σ_{2})) is the synchronization shuffle of Exp (P(Σ_{1})) and Exp (P(Σ_{2})) iff:
Definition 17 only presents the synchronization shuffle of two process expressions, which can be extended into the case of k(k≥2) expressions, denoted by . It can be defined by:
PROCESS CHARACTERISTIC ANALYSIS DURING DECOMPOSITION
Lemma 5: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2, …, k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}) and BP(*) be the set of the basic process sections of *, where *ε{Σ, Σ_{1},…, Σ_{k}}. For each BPεBP(Σ), .
Proof: It is easy to prove.
Lemma 5: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}). Exp(P(Σ)) = Exp (P(Σ_{1}))ΘExp (P(Σ_{2})).
Proof: First with Exp (P(Σ))⊆Exp (P(Σ_{1}))ΘExp (P(Σ_{2})) and then Exp (P(Σ_{1}))ΘExp (P(Σ_{2}))⊆Exp (P(Σ)).
Now, we prove that Exp (P(Σ))⊆Exp (P(Σ_{1}))ΘExp (P(Σ_{2})).
For any Φn(N)εExp(P(Σ)), let N = (B, E; G). Since Φn(N) is a process of Σ, according to the definition of ,
(1) 
(2) 
(3) 
(4) 
Thus, With the definition of Θ, Φn(N)ε Exp (P(Σ_{1}))ΘExp(P(Σ_{2})) and Exp(P(Σ))⊆Exp (P(Σ_{1}))ΘExp(P(Σ_{2})).
Now, we prove that Exp (P(Σ_{1}))ΘExp (P(Σ_{2}))⊆Exp (P(Σ)).
For any Φn(N)εExp (P(Σ_{1}))ΘExp(P(Σ_{2})), let Φn(N) be the number of the basic process sections contained by Φn(N). The conclusion can be proved by induction on Φn(N).
(1) While Φn(N) =1, Φn(N) is a basic process section and . With Lemma 5, Φn(N) εBP(P(Σ)) ⊆Exp(P(Σ)), so Exp (P(Σ_{1}))ΘExp (P(Σ_{2}))⊆Exp (P(Σ)).
(2) Suppose that the conclusion is correct while Φn(N)≤k, i.e., Exp (P(Σ_{1}))ΘExp (P(Σ_{2}))⊆ Exp (P(Σ)).
Now, we prove it is also correct while
With the definition of process expression, there are Φn(N)εExp (P(Σ_{1}))ΘExp (P(Σ_{2})) and such that , where o is the connection operation between basic process sections and . Now, it is proved by two cases of .
Case 1:If where i, jε{1, 2} and i ≠ j, then
(a) 
(b) 
(c) 
(d) 
Case 2:
Other parts can be proved like the cases in Case 1.
With Case 1 and 2, Exp (P(Σ_{1}))ΘExp (P(Σ_{2})) ⊆Exp (P(Σ)) is proved based on the supposition.
Exp (P(Σ)) = Exp (P(Σ_{1}))ΘExp (P(Σ_{2})) has been proved since Exp (P(Σ))⊆ Exp(P(Σ_{1}))ΘExp (P(Σ_{2})) and Exp (P(Σ_{1}))ΘExp (P(Σ_{2}))⊆Exp (P(Σ)).
Theorem 5: Let Σ_{i} = (S_{i}, T_{i}; F_{i}, M_{0i}) (iε{1, 2, …, k}) be the index decomposition net of a Petri net Σ = (S, T; F, M_{0}) .
Proof: Based on Lemma 5, the theorem can be proved by induction on k.
Theorem 5 is useful to obtain the process expression of a Petri net by the operation Θ between processes based on the process expressions of the index decomposition SNets. The method will be presented in next section.
A CONSTRUCTION METHOD FOR THE PROCESS EXPRESSION OF PETRI NET
Using the decomposition method, a Petri net Σ can be decomposed into a set of SNets Σ_{1}, Σ_{2}, …, Σ_{k}. The methods to obtain the process expressions of all kinds of SNets are presented in earlier. Theorem 5 indicates the relation between the process expression of the original Petri net and its index decomposition net systems. is the process expression of Σ, so a method to obtain the process expression of a Petri net can be presented, which is shown in Algorithm 1.
Algorithm 1 presents a method to construct the process expression of a given Petri net. The correctness and termination can be proved by the analysis in the last sections. It benefits the semantic expression of the process of a Petri net especially a structurecomplex net system. This method adopts a top to down process, in which a Petri net is decomposed into a set of SNets since the process expression of each SNet is easy to obtain. Based on the process expressions of these SNets, the process expression of the original Petri net can be expressed by the operation of Θ between processes.
Example 5: We take the Petri net Σ shown in Fig. 1 as an example to show the method proposed in Algorithm 1.
The first step in Algorithm 1 is to decompose Σ into a set of SNets, which has been discussed earlier and the index decomposition sets are shown in Fig. 2.
The second step is to obtain the process expression of each SNet. Σ_{1} has been discussed in example 4 and its process expression is Exp (P(Σ_{1})) = (P_{111} Ο P_{112})^{α}P_{113}*. Σ_{3} has been discussed in example 2 and its process expression is Exp (P(Σ_{3})) = P_{31}*.
Now, it is only necessary to obtain the process expression of Σ_{2}. There is a primitive transition t_{4} and a goal transition t_{2} in Σ_{2}. First, Σ_{2} is transformed into an SNet Σ`_{2} without goal transition. Σ`_{2} is an SNet satisfying the conditions in Theorem 4, so two new SNets are constructed first, which are Σ`_{21} and Σ`_{22} shown in Fig. 7. Σ`_{21} is an Sgraph and Σ`_{22} is an SNet with one and only one primitive transition and with empty initial markings.
Algorithm 1:  To obtain the process expression of a Petri net 
Fig. 7:  Two new SNets Σ`_{21} and Σ`_{22} 
Fig. 8:  The basic process section of Σ_{123} 
According to methods, as mentioned earlier the process expression of Σ`_{21} is Exp (P(Σ`_{21})) = P_{211}*Ο P_{212}, where the basic process sections P_{211} and P_{212} are shown in Fig. 8a. The part in P_{212} containing by a brokenline quadrangle should be deleted, since it is added in order to reduce the goal transition. The process expression of Σ`_{22} is Exp(P(Σ`_{22})) = (P_{221}Ο P_{222} Ο P_{223})^{α}. Similarly, the part in P_{223} contained by a brokenline quadrangle should also be deleted. So, the process expression of Σ`_{2} is:

The third step in Algorithm 1 is to output the process expression of Petri net Σ,
CONCLUSION
A construction method for the process expression of a Petri net is proposed based on the index decomposition. With this decomposition method, a Petri net is decomposed into a set of SNets. The process properties of the SNets are easy to analyze since they are wellformed and their process expressions are easier to obtain than the original Petri net. With the process expressions of the index decomposition nets, the process expression of the original Petri net can be presented by the synchronization shuffle operation between processes.
There have been lots of works to obtain the process expression of a Petri net (Wu, 1996; Wu et al., 2000; Zeng and Wu, 2003). The method introduce in Wu (1996) only suits the bounded Petri net and the method of Wu et al. (2000) only suits the unbounded but fair Petri net. Zeng and Wu (2003) presents the method can be used for all kinds of Petri nets, however it is necessary to obtain the process net system first. Since the structure of the process net system is usually complex, it must decompose the process net system so as to obtain its language expression. The process of the method in Zeng and Wu (2003) is very complex. Compared with the related work, the construction method proposed in this work is easier to realize and it is useful for obtaining the process expressions of all kinds of Petri nets.
The semantics of the process expression containing Θ is not obvious. In the future, the reduction and optimization for the process expression containing Θ must be considered. The applications of the process expression for analyzing the properties such as liveness and fairness are also research work in the future.
ACKNOWLEDGMENTS
Supported by the National Science Foundation of China under Grant No.60603090 and 90718011, the Excellent Young Scientist Foundation of Shandong Province of China under Grant No. 2006BS01019 and the Taishan Scholar Program of Shandong Province.
REFERENCES
 Garg, V.K. and M.T. Ragunath, 1992. Concurrent regular expressions and their relationship to Petri nets. Theor. Comput. Sci., 96: 285304.
CrossRef  Murata, T., 1989. Petri nets: Properties, analysis and applications. Proc. IEEE., 77: 541580.
CrossRefDirect Link  Wu, Z.H., 1996. Process expression of bounded petri nets. Sci. China Ser. ETechnol. Sci., 39: 3749.
CrossRefDirect Link  Wu, Z.H., P.L. Wang and M.X. Zhao, 2000. Process expression of unbounded fair Petri nets. Chinese J. Comput., 23: 337344.
Direct Link  Zeng, Q.T. and Z.H. Wu, 2002. Process net system of petri net. Chinese J. Comput., 25: 13071315.
Direct Link  Zeng, Q.T. and Z.H. Wu, 2003. Process expression of unbounded Petri net. Chinese J. Comput., 26: 16291636.
Direct Link  Zeng, Q.T. and Z.H.Wu, 2004. Methods for behavior descriptions of structurecomplex Petri nets. J. Control Theor. Applied, 2: 9398.
CrossRefDirect Link