Reachability Criterion with Sufficient Test Space for Ordinary Petri Net

1. Introduction

Petri nets (PN) are widely recognized as a powerful tool for modelling and analyzing discrete event systems, especially systems are characterized by synchronization, concurrency, parallelism and resource sharing [1, 2]. One of the major advantages of using Petri net models is that the PN model can be used for the analysis of behaviour properties and performance evaluation, as well as for systematic construction of discrete-event simulators and controllers [3, 4]. The reachability from an initial marking to a destination marking is the most important issue for the analysis of Petri nets. Many other problems such as liveness and coverability can be deduced from this reachability problem [5, 6].

Two basic approaches are usually applied to solve the reachability problem. One is the construction of reachability tree [7, 8]. It can obtain all the reachable markings, but the computation complexity is exponentially increased with the size of a PN. The other is to solve the state equation [9]. The solution of the matrix equation provides a firing count vector that describes the relation between initial marking and reachable markings. Its major problem is the lack of information of firing sequences and the existence of spurious solutions.

Many researchers have investigated the reachability problem [10, 11]. Iko Miyazawa et al. have utilized the state equation to solve the reachability problem of Petri nets with parallel structures [12]. Tadashi Matsumoto et al. have presented a formal necessary and sufficient condition on reachability of general Petri nets with known firing count vectors [13]. Tadao Murata’s paper has concentrated on presenting and analyzing Petri nets as discrete time systems. Controllability and reachability are analyzed in terms of the matrix representation of a Petri net [14].

In most cases, it is not necessary to find all reachable markings. One of the most important things is to know whether a given marking is reachable or not. If the destination marking M_d is reachable from the initial marking M₀, it is significant to find a firing sequence, which is an ordered sequence of transitions that lead M₀ to M_d. The following method can be utilized to find a reachable marking [15].

1. Solve the equation AX=M_d-M₀ to ascertain all the solutions X₁, X₂, … and construct the set X={X₁, X₂, …}.

2. Test if X_i in X is an executable solution from M₀, i.e. there is at least one sequence S(X_i) that is a firing sequence under M₀.

3. If an executable solution exists, then M_d is reachable. On the contrary, if X=Ф or all solutions are spurious, then M_d is not reachable.

However, this approach is theoretic rather than practical, because there are two problems: One is that the solution of the fundamental equation AX=M_d-M₀ is infinite in some cases. In that case, it is impossible to test all solution X_i. The other is that the computation complexity of testing X_i increases at least exponentially as the length of S(X_i) increases.

In this chapter, the above two problems will be solved as follows: First, we construct a sufficient test space to include at least one executable solution within set X. An approach is secondly proposed to test whether there is an executable solution within the sufficient test space or not. A systematic method to search an executable solution in a sufficient test space and to enumerate the associated firing sequence is presented.

The remainder of the chapter is arranged as follows: Definitions and notations required in this chapter are given in Section 2. Section 3 describes how to determine the sufficient test space for the reachability problem. In Section 4, an algorithm is developed to determine if X_i is a executable solution under M₀ and gives the associated firing sequence S(X_i). The illustrative examples are given in Section 3, Section 4, and Section 5.

2. Preliminaries

In this section, we present some definitions and notations to be necessary in the following sections.

Definition 1. Let PN=(P, T, I, O, M₀) be a marked Petri net. P={p₁, p₂, …, p_n} is the finite set of places. T={t₁, t₂, …, t_m} is the finite set of transitions. I is the input function. O is the output function. M₀ is the initial marking.

A PN is an ordinary Petri net iff I(p, t)→{0, 1} and O(t, p)→{0, 1} for any p∈P and t∈T. A=O-I is the incidence matrix, where O and I are the output and input function matrices [16]. Let X=[x₁ x₂ … x_m]^T be a column vector. If X is the firing count vector of S(X), the sequence S(X) is called the transition sequence associated with X. The transition set T(X) is called the support of X if it is composed of transitions associated with positive elements of X, i.e. T(X)={t_i|x_i>0}. p is the set of output transitions of p, p is the set of input transitions of p, t is the set of output places of t, and t is the set of input places of t.

Definition 2. C_i=<p, T_ci> is called a conflict structure [17] if it satisfies the following condition: T_ci={t|t∈p} and |T_ci|≥2, where |T_ci| is the cardinality of T_ci. We note that C={C₁, C₂, …} is the set of all C_i and T_c=T_c1∪T_c2∪…. is the set of all conflict transitions.

Definition 3. For transition t_j and X, the sub-vector H(t_j|X) is defined as: H(t_j|X)=e[t_j]x_j. e[t_j] is the unit m-vector which is zero everywhere except in the j-th element.

Definition 4. For the conflict structure C_i=<p, T_ci> and X, the sub-vector H(C_i|X) is defined as follows:

$$H({\text{C}}_{\text{i}}|X)={\displaystyle \sum _{\text{t j }\in \text{Tci}}H\text{(t j|}X\text{)}}$$E1

Definition 5. C_i=<p, T_ci> is in a spurious conflict state for X under M if there exists a firing sequence S(H(C_i|X)) under M, i.e. the mathematic criterion is M≥IH(C_i|X).

Otherwise, C_i is in an effective conflict state for X under M, and the transition in T_ci is called the effective conflict transition for X under M.

Notation 1. N(t_j|S(X))=x_j is the number of occurrence times of t_j in S(X).

Notation 2. If q=min{M(p_i), p_i∈t_j}, we call t_j q-enabled under marking M. This q is denoted as E(t_j|M).

Definition 6. F=[f₁ f₂ … f_m]^T is called an actual firing vector whose j-th element is f_j=min{N(t_j|S(X)), E(t_j|M)}. F can be partitioned into two parts as follows: F=F_o+F_c, where F_c=[f_c1 f_c2 … f_cm]^T is associated with effective conflict transitions, F_o =[f_o1 f_o2 … f_om]^T is associated with the other transitions. F_o and F_c satisfy the following conditions:

1. If t_j is an effective conflict transition for X under M, then f_oj=0 and f_cj=f_j.

2. Otherwise, f_cj=0 and f_oj=f_j.

3. Determination of the sufficient test space

If all the solutions of the equation AX=M_d-M₀ are tested, It can be found whether M_d is reachable or not. But in some case, the solutions are infinite. Therefore, the tested range is determined in order to keep the method practical. This range must be finite and include at least one executable solution if it exists. This section will discuss how to determine the tested range.

Definition 7. Given the initial marking M₀ and the destination marking M_d of a PN, X is a solution of AX=M_d-M₀. If M_d is reachable from M₀ under X, then X is called an executable solution. Otherwise, X is called a spurious solution.

Definition 8. X={X₁, X₂, … } is the set of a solution X, the subset X_e={X_e1, X_e2, … } of X is called the sufficient test space if it satisfies following conditions:

1. If Md is reachable from M0, there must exist at least one element in Xe which is executable solution; in other words, if all elements in Xe are not executable, then all the elements in X are not executable either.

2. Xe is a finite set.

Definition 9. The vector X which is a solution of AX=0 is known as a T-invariant [18]. A solution X is called positive if every element of X is nonnegative.

Definition 10. The positive T-invariant solution U of AU=0 is minimal if it satisfies the following condition: for any other T-invariant U_i, at least one element of U-U_i is negative. The set of minimal T-invariant solutions is U={U₁, U₂, …, U_s}.

Definition 11. The positive particular solution V of AV=M_d-M₀ is minimal if it satisfies the following condition: for any T-invariant U of PN, there must be at least one element in V-U which is negative, i.e. {U|V-U≥0, U is a T-invariant}=Ф. The set of minimal particular solutions is V={V₁, V_2, …, V_q}.

The general solution of AX=M_d-M₀ must be expressed by the form of one minimal particular solution and the arbitrary linear combination of the T-invariant solutions as follows:

$$X=V\text{i}+{\displaystyle \sum _{j=1}^{r}kjUj}$$E2

where V_i∈V, k_j is nonnegative integer.

Algorithm 1. Interpretation of the computation for X_e.

1. Solve the equation AX=0, get all the positive integer solutions U={U₁, U₂, …, U_s}, where each U_j (1js) is a minimal T-invariant.

2. Solve the equation AX=M_d-M₀, get all the positive integer particular solutions V={V₁, V_2, …, V_q}, where each V_i (1iq) is a minimal particular solution. B={B₁, B_2, …, B_n} is a subset of V.

If V= Ф, M_d is not reachable, then end.

1. Initialization: Let X_e=V={V₁, V₂ …, V_q} and X_temp= Ф.

If U= Ф, then end.

Otherwise, for every V_i, if T(V_i)T(U_j), then V_iB. If T(V_i)T(U_j), then V_iB.

Go to Step 4.

1. For each pair of (B_i, U_j), where i=1, 2, … |B|, j=1, 2, … s, and |B| is the cardinality of set B, carry out the following operations:

If T(B_i)∩T(U_j) = Ф, choose the next pair of (B_i, U_j).

If T(B_i)∩T(U_j) ≠ Ф and T(U_j)$$\subset$$ T(B_i), choose the next pair of (B_i, U_j).

If T(B_i)∩T(U_j) ≠ Ф and T(U_j)$$\not\subset$$ T(B_i), then D_i=B_i-max(B_i)U_j, where max(B_i) is the maximum value of elements in B_i.

Let D_i(r) be the r-th elememt of D_i.

W_i(r)=f(D_i(r)), where$$f(x)=\{\begin{array}{c}{D}_i(r),if{D}_i(r)>0\\ 0,⥄⥄⥄if{D}_i(r)\le 0\end{array}$$, r=1, 2, … m.

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{m}}\text{(}{W}_i\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_j\text{)}{}^{\circ }\text{}}\right|)}$$=β, where W_i(r) is the r-th element of W_i, m=|T|.

Add B_i+kU_j, k=1, 2, … β, to X_temp

When all pairs of (B_i, U_j) have been tested, go to Step 5.

1. If X_temp= Ф, then end.

Otherwise, Let B=X_temp, X_e=X_eB, X_temp= Ф, go to Step 4.

Step 1 and Step 2 are to determine all the positive integer solutions X for equation AX=M_d-M₀. The firing count vector of any firing sequence from M₀ to M_d belongs to X. In Step 4, if B_i is not an executable solution, then there must be some transitions in T(B_i) which aren’t enable it, i.e. some places in T(B_i) are lack of tokens. In this case, if {p|p∈T(B_i)∩T(U_j) and T(U_j)$$\not\subset$$ T(B_i)}≠ Ф, then T(U_j) may provide tokens for t, where t∈T(B_i). Consequently, B_i+kU_j may be an executable solution, where k=1, 2, … β. Since the number of places and transitions in PN is finite, Step 4 and Step 5 only add finite elements to X_e. Since the number of minimal T-invariants is finite, the finishing condition X_temp= Ф, i.e. |{p|p∈T(B_i)∩T(U_j) and T(U_j)$$\not\subset$$ T(B_i)}|= Ф, is satisfied after all the related T-invariants have been considered. As a result of the iterative process of Step 4→Step 5→Step 4, X_e includes at least one executable solution if it exists.

The following examples show how to implement the computation algorithm. These examples illustrate that suppressing any k_i in B_i+kU_j, k=1, 2, … β, may eliminate some possible executable solutions.

Example 1. When the initial marking is M₀=(1,0,0,0,0,1,0,0,0) and the destination marking is M_d=(1,0,0,0,0,0,0,0,1) in Figure 1, calculate the sufficient test space X_e. The ● and ○ symbols are represented as the initial and destination markings respectively.

1. Solve the equation AX=0, get the positive integer minimal T-invariant U₁=(1,1,1,1,0,0,0,0).

2. Solve the equation AX=M_d-M₀, get the positive integer minimal particular solution V={V}=(0,0,0,0,1,1,1,1)

3. Initialization: Let X_e=V, X_temp= Ф, B=X_e

Step 4-1.For (V, U₁),

If T(U₁)$$\not\subset$$ T(V), then D=V-max(V)U₁, W(r)=f(D(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{8}}\text{(}W\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_1\text{)}{}^{\circ }\text{}}\right|)}$$E3

=3.

Then add V+U₁, V+2U₁, V+3U₁ to the set of X_temp,

Therefore, X_temp={V+U₁, V+2U₁, V+3U₁}

Step 5-1.If X_temp≠Φ, then let B=X_temp={V+U₁, V+2U₁, V+3U₁}

X_e=X_eB={V, V+U₁, V+2U₁, V+3U₁}, X_temp=Φ.

Go to Step4 in Algorithm 1.

Step 4-2.For any pair of (B_i, U₁), T(U₁)$$\subset$$ T(B_i) is satisfied. Therefore, X_temp=Φ

Step 5-2.If X_temp=Φ, then end.

As a result of above sequence, M_d is reachable from M₀. The firing sequence is t₅*t₁*t₂*t₆*t₇*t₃*t₄*t₈. Its firing count vector corresponds to V+U₁=(1,1,1,1,1,1,1,1) in the sufficient test space X_e. This example shows that suppressing B_i+kU_j (k=1) in X_e may eliminate some possible executable solution.

Example 2. Consider the PN of Figure 2, given the initial marking M₀=(1,0,0,0,0,0,0,0,1,0) and the destination marking M_d=(0,0,0,1,0,0,0,0,1,0), calculate the sufficient test space X_e.

Figure 1.

Petri net structure

Figure 2.

Petri net structure

1. Solve the equation AX=0, two positive integer minimal T-invariants are obtained: U₁=(0,0,0,1,1,1,1,0,0,0), U₂=(0,0,0,0,0,0,0,0,1,1)

2. Solve the equation AX=M_d-M₀, get the positive integer minimal particular solutions V={V}={(1,1,1,0,0,0,0,1,0,0)}

The general solution can be expressed as follows:

$$X=\text{(1,1,1,0,0,0,0,1,0,0)}+\text{k}1\cdot \text{(0,0,0,1,1,1,1,0,0,0)}+\text{k2}\cdot \text{(0,0,0,0,0,0,0,0,1,1)}$$E4

k₁ and k₂ are nonnegative integer.

1. Initialization: Let X_e=V, X_temp=Φ, B=X_e

Step 4-1. For (V, U₁),

If T(U₁)$$\not\subset$$ T(V), then D=V-max(V)U₁, W(r)=f(D(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{10}}\text{(}W\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_1\text{)}{}^{\circ }\text{}}\right|)}$$E5

=2.

Then add V+U₁, V+2U₁ to X_temp. So X_temp={V+U₁, V+2U₁}

For (V, U₂),

If T(U₂)$$\not\subset$$ T(V), then D=V-max(V)U₂, W(r)=f(D(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{10}}\text{(}W\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_2\text{)}{}^{\circ }\text{}}\right|)}$$E6

=1.

Then add V+U₂ to X_temp. So X_temp={V+U₁, V+2U₁, V+U₂}

Step 5-1. If X_temp≠Φ, then let B=X_temp={V+U₁, V+2U₁, V+U₂},

X_e=X_eB={V, V+U₁, V+2U₁, V+U₂}. Let’s put X_temp=Φ.

Go to Step 4 in Algorithm 1.

Step 4-2.For (V+U₁, U₁), because T(U₁)T(V+U₁), choose the next pair.

For (V+U₁, U₂),

If T(U₂)$$\not\subset$$ T(V+U₁), then D₁=(V+U₁)-max(V+U₁)U₂, W₁(r)=f(D₁(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{10}}\text{(}{W}_{\text{1}}\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_2\text{)}{}^{\circ }\text{}}\right|)}$$E7

=2

.

Then add V+U₁+U₂ and V+U₁+2U₂ to X_temp. So X_temp={V+U₁+U₂, V+U₁+2U₂}

For (V+2U₁, U₁), because T(U₁)T(V+2U₁), choose the next pair.

For (V+2U₁, U₂),

If T(U₂)$$\not\subset$$ T(V+2U₁), then D₂=(V+2U₁)-max(V+2U₁)U₂, W₂(r)=f(D₂(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{10}}\text{(}{W}_{\text{2}}\text{)(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_2\text{)}{}^{\circ }\text{}}\right|)}$$E8

=3.

Then add V+2U₁+U₂, V+2U₁+2U₂, and V+2U₁+3U₂ to X_temp. So X_temp={V+U₁+U₂, V+U₁+2U₂, V+2U₁+U₂, V+2U₁+2U₂, V+2U₁+3U₂}

For (V+U₂, U₂), because T(U₂)T(V+U₂), choose the next pair.

For (V+U₂, U₁),

If T(U₁)$$\not\subset$$ T(V+U₂), then D₃=(V+U₂)-max(V+U₂)U₁, W₃(r)=f(D₃(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{10}}\text{(}{W}_{\text{3}}\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}{U}_1\text{)}{}^{\circ }\text{}}\right|)}$$E9

=3.

Then add V+U₂+U₁, V+U₂+2U₁, and V+U₂+3U₁ to X_temp. So X_temp={V+U₁+U₂, V+U₁+2U₂, V+2U₁+U₂, V+2U₁+2U₂, V+2U₁+3U₂, V+U₂+3U₁}

Step 5-2.If X_temp≠Φ, then let B=X_temp={V+U₁+U₂, V+U₁+2U₂, V+2U₁+U₂, V+2U₁+2U₂, V+2U₁+3U₂, V+U₂+3U₁}.

So, X_e=X_e+B={V, V+U₁, V+2U₁, V+U₂, V+U₁+U₂, V+U₁+2U₂, V+2U₁+U₂, V+2U₁+2U₂, V+2U₁+3U₂, V+U₂+3U₁}. Let’s put X_temp=Φ.

Go to Step 4 in Algorithm 1.

Step 4-3.For any pair of (B_i, U_j), because T(U_j) T(B_i), X_temp=Φ

Step 5-3.If X_temp=Φ, then end

M_d is reachable from M₀. The firing sequence is t₉*t₇*t₄*t₁*t₅*t₆*t₇*t₂*t₄*t₅*t₆*t₁₀*t₃*t₈. Its firing count vector corresponds to V+2U₁+U₂=(1,1,1,2,2,2,2,1,1,1) in the sufficient test space X_e. This example illustrates that suppressing B_i+kU_j (k=β) in X_e may eliminate some possible executable solution.

4. Search of a firing sequence

Given the initial marking M₀ and the destination marking M_d of a PN, a solution X_ei is solved from AX=M_d-M_0. Then, an algorithm is developed to determine whether M_d is reachable from M₀ under X_ei or not. If M_d is reachable from M₀, the algorithm gives the associated firing sequence S(X_ei).

Definition 12. Let S= t₁t₂…t_r be a finite transition sequence. The transitions appearing in S are defined by the set Z(S) ={t₁, t₂, …, t_r}. The set of transitions Z(S) is called a sequence component. Z(S) is the set of elements that appear in a transition sequence S.

Algorithm 2. Search of a firing sequence S(X_ei) under M₀

1. According to I, determine all the conflict structure C_i=<p, T_ci>, and construct T_c and C.

2. Initialization: Let M=M₀, X=X_ei, S=λ (λ is the sequence of length zero)

3. Under M and X, calculate F=F_o+F_c from Definition 6.

If F_o≠0, go to Step 4.

If F_o =0 and F_c≠0, go to Step 5.

If F=0, go to step 6.

Step 4. If F_o≠0, then there exists an S(F_o) that has a firing sequence under M. Therefore, S(F_o) can be fired. The reachable marking is calculated by M’=M-AF_o,

Let M=M’, X=X–F_o, S=S*S(F_o), where * is concatenation operation and S*S(F_o) means S followed by S(F_o). Go to Step 3.

1. F_o =0 and F_c≠0 means that all transitions in S(F_c) are effective conflict transitions. Therefore, branching occurs and the number of branches is |T(F_c)|. From here, the computation has to consider all |T(F_c)| branches.

After selecting a transition t_j∈T(F_c), fire it, then the reachable marking is calculated by M’=M-Ae[t_j].

Let M=M’, X=X–e[t_j], S=S*t_j.Go to Step 3

Step 6. If X=0, then M_d is reachable from M₀ and S=S(X_ei) is one of the firing sequences, end. Otherwise, go to Step 7.

1. If all the branches in Step 5 have been implemented, then M_d is not reachable, end. Otherwise, go to Step 5 and implement the remaining branches.

The validity of the above algorithm is proved as the following four cases:

Base: Let X be a solution of AX=M_d-M₀. The actual firing vector F=F_o+F_c is obtained with M and X. Let t_o∈T(F_o) and t_c∈T(F_c).

Case 1: If F_o≠0 and F_c=0, then multiple firing of S(F_o) doesn’t affect a firing sequence associated with X under M₀, for the input places of T(F_o) don’t affect the enabling condition of other transitions in T(X) except transitions in T(F_o).

Case 2: If F_o=0 and F_c≠0, then the firing of each transition in S(F_c) is considered as a branch and implemented with respect to all branches. It means that all possibilities are involved. So, Algorithm 2 doesn’t eliminate any possible firing sequence.

Case 3: If F_o=0 and F_c=0, then no transition is enabled.

Case 4: If F_o≠0 and F_c≠0, then the multiple firing of S(F_o) can be implemented before S(F_c). It doesn’t eliminate any probability of finding a firing sequence associated with X under M₀. It is proven in Proposition 1.

Proposition 1. If σ∈S(X) is a firing sequence under M₀, then (S(F_o)*σ’)∈S(X) is a firing sequence under M₀ for any sequence σ’.

Proof:

1. Let T(F_o)={t_o1, t_o2, …, t_on}. For a transition t_o1∈T(F_o), σ can be represented as σ =σ₁*t_o*σ₂, where t_o1Z(σ₁). Then M₀$$\stackrel{{\text{σ}}_{\text{1}}}{\to }$$M₁$$\stackrel{{\text{t}}_{\text{o1}}}{\to }$$M₂$$\stackrel{{\text{σ}}_{\text{2}}}{\to }$$M_d is a firing sequence. Since T(F_o) is the set of transitions possible to be enabled under M₀, M₀ enables t_o1. Therefore it is possible to put M₀$$\stackrel{{\text{t}}_{\text{o1}}}{\to }$$M₃. By the definition of F_o, we have M₃(p)≥M₀(p) for any p∈Z(σ₁). So σ₁ is enabled under M₃ because σ₁ is enabled under M₀ (Monotonicity Lemma). After σ₁ firing, M₂ is reachable from M₃. Therefore, we have M₀$$\stackrel{{\text{t}}_{\text{o1}}}{\to }$$M₃$$\stackrel{{\text{σ}}_{\text{1}}}{\to }$$M₂. Since σ₂ is enabled under M₂, t_o1*σ₁*σ₂ is a firing sequence under M₀.

2. Under M₃, let’s consider the new T(F_o)={t_o2, …, t_on}T(F_o’), where T(F_o’) is the set of transition generated after t_o1 firing and may be empty. For a transition t_o2∈T(F_o), σ₁*σ₂ can be represented as σ₁*σ₂=σ₃*t_o2*σ₄, where t_o2Z(σ₃). Then σ₃*t_o2*σ₄ is a firing sequence. By the same way described in Step 1, we can prove that t_o2*σ₃*σ₄ is a firing sequence under M₃.

3. By Step 1 and Step 2, t_o1*t_o2*σ₃*σ₄ is a firing sequence under M₀.

4. In the same way, it is proven that t_o1*t_o2*…*t_on*σ_i*σ_j is a firing sequence under M₀. According to the definition of F_o, all transitions in {t_o1, t_o2, …, t_on} can fire simultaneously under M₀. Let’s put σ’=σ_i*σ_j, then (S(F_o)*σ’)∈S(X) is a firing sequence under M₀.

Example 3. Let us now apply the proposed algorithm to the PN of Figure 3. Given M₀=(0,0,0,0,0,0,1,0,0), M_d=(0,0,0,0,1,0,1,0,0) and X=(1,2,1,1,1,1,1), determine if M_d is reachable or not under M₀ and X.

Figure 3.

Petri net structure

1. There are two conflict structures, C₁=<p₁, {t₂, t₅}>, C₂=<p₂, {t₃, t₄}>, T_c={t₂, t₃, t₄, t₅}.

2. Initialization: M=M₀= (0,0,0,0,0,0,1,0,0), X=X=(1,2,1,1,1,1,1), S=λ

3. Under M and X, only t₆ is 1-enabled. Then, F_o=(0,0,0,0,0,1,0).

4. Fire S(F_o)= t₆. Then the reachable marking M’ becomes (1,0,0,0,0,0,0,1,0)

Let M=M’, X=X-F_o=(1,2,1,1,1,0,1), S=t₆. Go to Step 3 in Algorithm 2.

Step 3-1.Under M and X, F_o=(0,0,0,0,0,0,1).

Step 4-1.Fire S(F_o)=t₇. Then, the reachable marking becomes M’=(1,0,0,0,0,0,1,0,1)

Let M=M’, X=X-F_o=(1,2,1,1,1,0,0), S=t₆*t₇. Go to Step 3 in Algorithm 2.

Step 3-2.Under M and X, F_o=(0,1,0,0,0,0,0). Go to Step 4 in Algorithm 2.

Step 4-2.Fire S(F_o)=t₂ (t₂ is not an effective conflict transition because t₅ cannot enable),

then the reachable marking becomes M’=(0,1,0,0,1,0,1,0,1)

Let M=M’, X=X-F_o=(1,1,1,1,1,0,0), S= t₆*t₇*t₂. Go to Step 3 in Algorithm 2.

Step 3-3.Under M and X, F_o=(0,0,1,0,0,0,0). Go to Step 4 in Algorithm 2.

Step 4-3.Fire S(F_o)=t₃ (t₃ is not an effective conflict transition because t₄ cannot enable),

then the reachable marking becomes M’=(0,0,1,0,1,0,1,0,1)

Let M=M’, X=X-F_o=(1,1,0,1,1,0,0), S= t₆*t₇*t₂*t₃. Go to Step 3 in Algorithm 2.

Step 3-4.Under M and X, F=0, go to Step 6 in Algorithm 2.

Step 6.Because X≠0, go to Step 7 in Algorithm 2.

Step 7.There is no effective conflict transition i.e., no branch. Consequently, M_d is not reachable under X because X≠0.

The above implementing process can be presented by a firing path tree as shown in Figure 4.

5. Application of Reachability Criterion

An example will be given to illustrate how to use the proposed method of Algorithm 1 and Algorithm 2 to solve the reachability problem.

Example 4. When the initial marking is M₀=(1,0,0,0,0,0,0,0,1) in the PN of Figure 5, is the destination marking M_d=(0,0,1,0,1,0,0,0,1) reachable from M₀ ?

First, calculate sufficient test space using the following steps:

1. Solve the equation AX=0, get one positive integer minimal T-invariant U=(0,0,0,0,0,0,1,1).

2. Solve the equation AX=M_d-M₀, get the positive integer minimal particular solutions V₁=(0,2,1,0,2,2,0,0), V₂=(2,2,1,2,0,0,0,0) and V₃=(1,2,1,1,1,1,0,0)

3. Initialization: Let X_e={V₁, V₂, V₃}, X_temp=Φ, B=X_e

Step 4-1 For (V₁, U),

Figure 4.

Firing path tree on reachability of Figure 3.

Figure 5.

Petri net structure

If T(U)$$\not\subset$$ T(V₁), then D₁=V₁-max(V₁)U, W₁(r)=f(D₁(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{8}}\text{(}{W}_1\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}U\text{)}{}^{\circ }\text{}}\right|)}=2$$E10

Then add V₁+U, V₁+2U to X_temp. Then, X_temp={V₁+U, V₁+2U }

For (V₂, U), because T(V₂)∩T(U) =Φ, choose the next pair.

For (V₃, U),

If T(U)$$\not\subset$$ T(V₃), then D₃=V₃-max(V₃)U, W₃(r)=f(D₃(r)),

$${\displaystyle \sum _{\text{r}=\text{1}}^{\text{8}}\text{(}{W}_{\text{3}}\text{(r)}\cdot \left|\text{{p|p}\in {}^{\circ }\text{t}{}_{\text{r}}\cap \text{T(}U\text{)}{}^{\circ }\text{}}\right|)}=1$$E11

Then add V₃+U to X_temp, X_temp={V₁+U, V₁+2U, V₃+U}

Step 5-1 If X_temp≠Φ, then let B=X_temp={V₁+U, V₁+2U, V₃+U},

X_e=X_eB={V₁, V₂, V₃, V₁+U, V₁+2U, V₃+U }. Let’s put X_temp=Φ. Go to Step 4 in Algorithm 1.

1. For any pair of (B_i, U), because T(U_j)$$\subset$$ T(B_i), X_temp=Φ.

2. If X_temp=Φ, then end.

Consequently, the sufficient test space becomes X_e={V₁, V₂, V₃, V₁+U, V₁+2U, V₃+U}.

Second, calculate a firing sequence in order to test if M(d) is reachable from M(0) under some element in X_e

The elements of the sufficient test space X_e are calculated separately as follows:

1. For X=V₁=(0,2,1,0,2,2,0,0)

The implementing process is shown in Figure 6.

1. For X=V₂=(2,2,1,2,0,0,0,0)

Carrying out the same process, the conclusion is as follows: M_d is not reachable under V₂.

1. For X=V₃=(1,2,1,1,1,1,0,0)

Carrying out the same process, the conclusion is as follows: M_d is not reachable under V₂.

1. For X=V₁+U=(0,2,1,0,2,2,1,1)

Carrying out the same process shown in Figure 7, the conclusion is as follows: M_d is reachable from M₀ under V₁+U. V₁+U is an executable solution in X_e, and the firing sequence is t₅*t₇*t₆*t₂*t₃*t₅*t₆*t₂*t₈.

As a result of calculating each element of the sufficient test space X_e={V₁, V₂, V₃, V₁+U, V₁+2U, V₃+U} individually, a firing sequence is finally found at the fourth element (V₁+U) of X_e. Therefore, the elements V₁+2U and V₃+U don’t need to be calculated. Consequently, the structure of the Petri net (Figure 5) is shown to possess at least one reachable firing sequence.

Figure 6.

Firing path tree for V_1.

Figure 7.

Firing path tree for V₁+F.

6. Conclusions

In this chapter, a new general criterion has been created to solve the reachability problems for ordinary Petri nets. This criterion is based on two processes: (i) Calculating the sufficient test space. (ii) Testing whether or not the destination marking is reachable from the initial marking under the sufficient test space. The sufficient test space significantly reduces the quantity of computation needed to search for an executable solution in X. The firing path tree shows the firing sequence of an executable solution. Consequently, if the destination marking is reachable from the initial marking, this method gives at least one firing sequence that leads from the initial marking to the destination marking. Some examples are given to illustrate how to use this method to solve the reachability problem. This algorithm can be utilized in the following fields: Path searching, auto routing, and reachability between any places in a complicated network.