A Construction Method for the Process Expression of Petri Net Based on Decomposition

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 one-to-one 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 structure-complex Petri nets since the structure of the decomposition net is well-formed (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 S-Net (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₁ = (S, T; F) be a net and N₂ = (B, E; G) be an occurrence net. A mapping Φn: B • E→S • T is a mapping from N₂ to N₁, denoted by Φn: N₂→N₁, 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₁, M₀) = (S, T; F, M₀) 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₁ and satisfies the following conditions:

(1)	∀b1, b2εB:(b1≠b2): Φn(b1) = Φn(b2)→•b1≠Cb2 ∧b1•…b2• and
(2)	∀s ε S:|{b| Φn(b) = sΛ •b = φ} |≤M0 (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 = φ} |=M0 (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₁ and u₂ be two S-cuts of N such that u₁≤u₂. We define N₁ = (B₁,E₁; G₁) such that:

(1)	B1={x εB|∃b1εu1, b2εu2: (b1, x) εG*Λ(x, b2)εG*};
(2)	E1={y εE|∃b1εu1, b2εu2: (b1, y) εG*Λ(y, b2)εG*};
(3)	G1 = G∩ ({B1xE1} •{E1xB1})

If Φn₁: N₁→Σ satisfies ∀xε B₁•E₁: Φn₁(x) = Φn(x), (N, Φn₁) is said to be a section (between u₁ and u₂) of process P, sometimes it is also called a process section of Σ, denoted by (N[u₁, u₂], Φn) (Zeng and Wu, 2002c).

Definition 6: Let P = (N, Φn) be a surjective process of Σ and P₁ = (N[u₁, u₂], Φn) be a process section of Σ. If any two s-cuts u_i and u_j (i, j≠1,2) in N[u₁, u₂] satisfies:

then P₁ = (N[u₁, u₂], Φ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₁, u₂], Φn) be a basic process section of a Petri net Σ = (S, T; F, M₀) and Φn be the mapping from the occurrence net N = (B, E; G) to Σ.

(1)The sets ⁰P = {s|sεSΛΦn^-1 (s)εu₁} and

P⁰ = {s|sεSΛΦn^-1(s)εu₂} are respectively named as the input and the output place set of P.

(2)The bag B(⁰P) = {s|sεSΛΦn^-1 (s)εu₁} is the input place bag of P, where

Similarly, the bag B(P⁰) = {s|sεSΛΦn^-1 (s)εu₂} 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₀) be a Petri net. ∀Mε R(M₀), S₁⊆S, the projection of M on S₁ (denoted by is defined by for all sεS₁.

Definition 10: Let Φn be a mapping from the occurrence net N = (B, E; G) to the Petri net Σ = (S, T; F; M₀) 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 one-to-one mapping ξ: TP→BP(Σ) such that ∀tεTP, ξ (t)εBP(Σ);

(3)

(4)	Mop = ΓS→Sp (M0)

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₀), 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 structure-complex Petri net based on the indexes of places (Zeng and Wu, 2002a, 2004a, b).

Definition 12: Let Σ = (S, T; F, M₀) 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₁, s₂εS,

f (s) is named as the index of place s (Zeng and Wu, 2002a).

Definition 13: Let Σ = (S, T; F, M₀) 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 structure-complex 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₀) is an S-Net 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₀), then Σ_i is an S-net (Zeng and Wu, 2002a).

Accroding to Theorem 1, each of the index decomposition nets is well-formed 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 structure-complex 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₁) = f (s₆) = 1, f(s₂) = f(s₃) = 2, f(s₄) = f(s₅) = f (s₇) = 3.

Fig. 1:	A Petri net Σ

Fig. 2:	Three S-Nets 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 Σ₁, Σ₂ and Σ₃ are obtained and shown in Fig. 2. Obviously,Σ₁, Σ₂ and Σ₃ are S-Nets.

PROCESS EXPRESSIONS OF THE DECOMPOSITION NET SYSTEMS

According to Theorem 1, each index decomposition net system is an S-Net. We have analyzed the language and liveness characteristics of an S-Net, respectively in Zeng and Wu (2002b) and Duan and Zeng (2004). Here, we analyze the process characteristics of an S-Net (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 S-Net Σ, 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 S-Net Σ = (S, T; F, M₀). Σ_P is also an S-Net.

Definition 15: Let Σ = (S, T; F, M₀) be an S-Net. ∀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 S-Net with goal transitions into one S-Net without goal transitions. The method is to add an output place for each goal transition in the original S-Net. If we delete all the added places from all the processes of the new S-Net without goal transitions, it can keep all states and behaviors of the original S-Net invariant. Thus, the process semantics can be regarded as equal between the original S-Net and the new S-Net 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 S-Nets without goal transitions can be classified into four classes based on the standards of primitive transitions and initial markings. These four kinds of S-Nets, respectively are:

CS-Nets without primitive transitions and with empty markings. This kind of S-Nets has no any process, so it is not necessary to discuss.

CS-Nets without primitive transitions but with initial markings. It is obvious that this kind of S-Nets is S-graph (state machine). Without interpretations, this kind of S-Nets is named as S-graph directly in the following discussions.CS-Nets with primitive transitions but with empty initial markings. Without interpretations, this kind of S-Nets is named as S-Net with Empty Markings directly in the following discussions.

CS-Nets with primitive transitions and with initial markings. Without interpretations, this kind of S-Nets is named as S-Net with Initial Markings directly in the following discussions.

Next, we will discuss the process characteristics of each kind of the S-Nets based on the classification and present the method to obtain their process expression.

PROCESS EXPRESSION OF S-GRAPH

Lemma 1: Each S-Graph is bounded (Yuan, 2005).

Lemma 2: The process expression of each S-Graph 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₀). Exp (P(Σ_i)) is a regular expression if Σ_i is an S-Graph.Example 2: Σ₃ shown in Fig. 2c is an S-Net. Based on its reachability graph, we can obtain the set of the basic process sections of Σ₃. The method to obtain the basic process sections can be seen in Wu (1996). BP(Σ₃) = {P₃₁}and P₃₁ 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 Σ₃ is Exp (P(Σ₃)) = P₃₁*. It can be shown that each surjective process of Σ₃ is the prefix of the language of Exp (P(Σ₃)) = P₃₁*.

Fig. 3:	The basic process section of Σ3

PROCESS EXPRESSION OF S-NET 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₀). If there is one and only one primitive transition t`εT_i and ∀sεS: M₀ (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₀). If there is one and only one primitive transition t`εT_i and ∀sεS: M₀ (s) = 0 in Σ_i, there is a regular expression RE such that Exp (P(Σ₃)) = (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 S-Cut 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)	TiP = BP (Σi) and
(3)	FiP = {(u1j, Pj)|(Pj εBP(Σi)}•{(Pj, u2j)| Pj εBP(Σi)}, where P1 = (N[u11, u21], Φn) is the source process section of Σ and u11 = φ. So, (u11, P1) ⊕ FP . and
(4)	∀sεSP: M0P (s) = 0.

According to Lemma 1 and 2, Σ_iP is an S-Net 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 one-to-one 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 S-Net Σ₁₁ 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 S-Net Σ11 and its two basic precess sections

The process expression of Σ₁₁ is Exp (P(Σ₁₁)) = (P₁₁₁ P₁₁₂)^α, which can be obtained based on the process net system of Σ₁₁. It can be shown that each surjective process of Σ₁₁ is the prefix of the language of Exp (P(Σ₁₁)) = (P₁₁₁Ο P₁₁₂)^α, 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₁, …, t_n (n≥2) and ∀sεS_i M₀ (s) = 0 in Σ_i, there are regular expressions RE₁, …, RE_n such that Exp (P(Σ_i)) = (RE₁)^α||…|| (RE_n)^α.

Proof: Let T₀ = {t₁, …, t_n}. To construct S-Nets Σ_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₀-{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₁, …, RE_n such that Exp (P(Σ_i)) = (RE₁)^α ||…|| (RE_n)^α.

PROCESS EXPRESSION OF S-NET 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₀). If there are primitive transitions t₁, …, t_n (n≥1 and {t₁, …, t_n}⊆T_i) and at least one place s ε S such that M_0i (s) ≠ 0 in Σ_i, there are regular expressions RE₁,… , RE_n and RE_n+1 such that Exp (P(Σ_i)) = (RE₁)^α ||…|| (RE_n)^α|| RE_n+1.

Fig. 5:	The basic process section of Σ12

Proof: Let T₀ = {t₁, …, t_n}. To construct two S-Nets Σ_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 S-graph. With Theorem 3, there are regular expressions RE₁, …, RE_n such that Exp (P(Σ_i1)) = (RE₁)^α ||…||(RE_n)^α. With Theorem 1, Exp (Σ_i2) is a regular expression. So, there are regular expressions RE₁, …, RE_n and RE_n+1 such that Exp (P(Σ_i) = (RE₁)^α ||…||(RE_n)^α ||RE_n+1.

Example 4: We take the index decomposition net Σ₁ shown in Fig. 2a as an example. Two new S-Nets Σ₁₁ and Σ₁₂ are constructed and shown in Fig. 5a and b, respectively. Σ₁₁ is the S-Net shown in Fig. 4, so Exp (P(Σ₁₁)) = (P₁₁₁Ο P₁₁₂)^α. Σ₁₂ is an S-graph and Exp (P(Σ₁₂)) = P₁₁₃*, where the basic process section P₁₁₃ is shown in Fig. 6. So, the process expression of Σ₁ is Exp (P(Σ₁)) = Exp (P(Σ₁₁)) || Exp (P(Σ₁₂)) = (P₁₁₁Ο P₁₁₂)^α || P₁₁₃*.

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₀) and SN(*) be the set of occurrence net, where *ε{Σ, Σ₁, …, Σ_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(Σ₁))ΘExp (P(Σ₂)) is the synchronization shuffle of Exp (P(Σ₁)) and Exp (P(Σ₂)) 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₀) and BP(*) be the set of the basic process sections of *, where *ε{Σ, Σ₁,…, Σ_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₀). Exp(P(Σ)) = Exp (P(Σ₁))ΘExp (P(Σ₂)).

Proof: First with Exp (P(Σ))⊆Exp (P(Σ₁))ΘExp (P(Σ₂)) and then Exp (P(Σ₁))ΘExp (P(Σ₂))⊆Exp (P(Σ)).

Now, we prove that Exp (P(Σ))⊆Exp (P(Σ₁))ΘExp (P(Σ₂)).

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(Σ₁))ΘExp(P(Σ₂)) and Exp(P(Σ))⊆Exp (P(Σ₁))ΘExp(P(Σ₂)).

Now, we prove that Exp (P(Σ₁))ΘExp (P(Σ₂))⊆Exp (P(Σ)).

For any Φn(N)εExp (P(Σ₁))ΘExp(P(Σ₂)), 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(Σ₁))ΘExp (P(Σ₂))⊆Exp (P(Σ)).

(2) Suppose that the conclusion is correct while |Φn(N)|≤k, i.e., Exp (P(Σ₁))ΘExp (P(Σ₂))⊆ Exp (P(Σ)).

Now, we prove it is also correct while

With the definition of process expression, there are Φn(N)εExp (P(Σ₁))ΘExp (P(Σ₂)) 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(Σ₁))ΘExp (P(Σ₂)) ⊆Exp (P(Σ)) is proved based on the supposition.

Exp (P(Σ)) = Exp (P(Σ₁))ΘExp (P(Σ₂)) has been proved since Exp (P(Σ))⊆ Exp(P(Σ₁))ΘExp (P(Σ₂)) and Exp (P(Σ₁))ΘExp (P(Σ₂))⊆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₀) .

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 S-Nets. 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 S-Nets Σ₁, Σ₂, …, Σ_k. The methods to obtain the process expressions of all kinds of S-Nets 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 structure-complex net system. This method adopts a top to down process, in which a Petri net is decomposed into a set of S-Nets since the process expression of each S-Net is easy to obtain. Based on the process expressions of these S-Nets, 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 S-Nets, 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 S-Net. Σ₁ has been discussed in example 4 and its process expression is Exp (P(Σ₁)) = (P₁₁₁ Ο P₁₁₂)^α||P₁₁₃*. Σ₃ has been discussed in example 2 and its process expression is Exp (P(Σ₃)) = P₃₁*.

Now, it is only necessary to obtain the process expression of Σ₂. There is a primitive transition t₄ and a goal transition t₂ in Σ₂. First, Σ₂ is transformed into an S-Net Σ`<sub>2</sub> without goal transition. Σ`₂ is an S-Net satisfying the conditions in Theorem 4, so two new S-Nets are constructed first, which are Σ`<sub>21</sub> and Σ`₂₂ shown in Fig. 7. Σ`<sub>21</sub> is an S-graph and Σ`₂₂ is an S-Net 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 S-Nets Σ`21 and Σ`22

Fig. 8:	The basic process section of Σ123

According to methods, as mentioned earlier the process expression of Σ`<sub>21</sub> is Exp (P(Σ`₂₁)) = P₂₁₁*Ο P₂₁₂, where the basic process sections P₂₁₁ and P₂₁₂ are shown in Fig. 8a. The part in P₂₁₂ containing by a broken-line quadrangle should be deleted, since it is added in order to reduce the goal transition. The process expression of Σ`<sub>22</sub> is Exp(P(Σ`₂₂)) = (P₂₂₁Ο P₂₂₂ Ο P₂₂₃)^α. Similarly, the part in P₂₂₃ contained by a broken-line quadrangle should also be deleted. So, the process expression of Σ`₂ is:

The third step in Algorithm 1 is to output the process expression of Petri net Σ,