Open access peer-reviewed chapter

Reachability Criterion with Sufficient Test Space for Ordinary Petri Net

By Gi Bum Lee, Han Zandong and Jin S. Lee

Submitted: December 3rd 2011Reviewed: June 7th 2012Published: August 29th 2012

DOI: 10.5772/50518

Downloaded: 979

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 Md is reachable from the initial marking M0, it is significant to find a firing sequence, which is an ordered sequence of transitions that lead M0 to Md. The following method can be utilized to find a reachable marking [15].

  1. Solve the equation AX=Md-M0 to ascertain all the solutions X1, X2, … and construct the set X={X1, X2, …}.

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

  3. If an executable solution exists, then Md is reachable. On the contrary, if X=Ф or all solutions are spurious, then Md 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=Md-M0 is infinite in some cases. In that case, it is impossible to test all solution Xi. The other is that the computation complexity of testing Xi increases at least exponentially as the length of S(Xi) 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 Xi is a executable solution under M0 and gives the associated firing sequence S(Xi). 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, M0) be a marked Petri net. P={p1, p2, …, pn} is the finite set of places. T={t1, t2, …, tm} is the finite set of transitions. I is the input function. O is the output function. M0 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=[x1 x2 … xm]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)={ti|xi>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. Ci=<p, Tci> is called a conflict structure [17] if it satisfies the following condition: Tci={t|t∈p} and |Tci|≥2, where |Tci| is the cardinality of Tci. We note that C={C1, C2, …} is the set of all Ci and Tc=Tc1∪Tc2∪…. is the set of all conflict transitions.

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

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

H(Ci|X)=t j  TciH(t j|X)E1

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

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

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

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

Definition 6. F=[f1 f2 … fm]T is called an actual firing vector whose j-th element is fj=min{N(tj|S(X)), E(tj|M)}. F can be partitioned into two parts as follows: F=Fo+Fc, where Fc=[fc1 fc2 … fcm]T is associated with effective conflict transitions, Fo =[fo1 fo2 … fom]T is associated with the other transitions. Fo and Fc satisfy the following conditions:

  1. If tj is an effective conflict transition for X under M, then foj=0 and fcj=fj.

  2. Otherwise, fcj=0 and foj=fj.

3. Determination of the sufficient test space

If all the solutions of the equation AX=Md-M0 are tested, It can be found whether Md 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 M0 and the destination marking Md of a PN, X is a solution of AX=Md-M0. If Md is reachable from M0 under X, then X is called an executable solution. Otherwise, X is called a spurious solution.

Definition 8. X={X1, X2, … } is the set of a solution X, the subset Xe={Xe1, Xe2, … } 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 Ui, at least one element of U-Ui is negative. The set of minimal T-invariant solutions is U={U1, U2, …, Us}.

Definition 11. The positive particular solution V of AV=Md-M0 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={V1, V2, …, Vq}.

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

X=Vi+j=1rkjUjE2

where Vi∈V, kj is nonnegative integer.

Algorithm 1. Interpretation of the computation for Xe.

  1. Solve the equation AX=0, get all the positive integer solutions U={U1, U2, …, Us}, where each Uj (1js) is a minimal T-invariant.

  2. Solve the equation AX=Md-M0, get all the positive integer particular solutions V={V1, V2, …, Vq}, where each Vi (1iq) is a minimal particular solution. B={B1, B2, …, Bn} is a subset of V.

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

  1. Initialization: Let Xe=V={V1, V2 …, Vq} and Xtemp= Ф.

If U= Ф, then end.

Otherwise, for every Vi, if T(Vi)T(Uj), then ViB. If T(Vi)T(Uj), then ViB.

Go to Step 4.

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

If T(Bi)∩T(Uj) = Ф, choose the next pair of (Bi, Uj).

If T(Bi)∩T(Uj) ≠ Ф and T(Uj)T(Bi), choose the next pair of (Bi, Uj).

If T(Bi)∩T(Uj) ≠ Ф and T(Uj)T(Bi), then Di=Bi-max(Bi)Uj, where max(Bi) is the maximum value of elements in Bi.

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

Wi(r)=f(Di(r)), wheref(x)={Di(r),ifDi(r)>00,ifDi(r)0, r=1, 2, … m.

r=1m(Wi(r)|{p|ptrT(Uj)}|)=β, where Wi(r) is the r-th element of Wi, m=|T|.

Add Bi+kUj, k=1, 2, … β, to Xtemp

When all pairs of (Bi, Uj) have been tested, go to Step 5.

  1. If Xtemp= Ф, then end.

Otherwise, Let B=Xtemp, Xe=XeB, Xtemp= Ф, go to Step 4.

Step 1 and Step 2 are to determine all the positive integer solutions X for equation AX=Md-M0. The firing count vector of any firing sequence from M0 to Md belongs to X. In Step 4, if Bi is not an executable solution, then there must be some transitions in T(Bi) which aren’t enable it, i.e. some places in T(Bi) are lack of tokens. In this case, if {p|p∈T(Bi)∩T(Uj) and T(Uj)T(Bi)}≠ Ф, then T(Uj) may provide tokens for t, where t∈T(Bi). Consequently, Bi+kUj 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 Xe. Since the number of minimal T-invariants is finite, the finishing condition Xtemp= Ф, i.e. |{p|p∈T(Bi)∩T(Uj) and T(Uj)T(Bi)}|= Ф, 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, Xe 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 ki in Bi+kUj, k=1, 2, … β, may eliminate some possible executable solutions.

Example 1. When the initial marking is M0=(1,0,0,0,0,1,0,0,0) and the destination marking is Md=(1,0,0,0,0,0,0,0,1) in Figure 1, calculate the sufficient test space Xe. 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 U1=(1,1,1,1,0,0,0,0).

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

  3. Initialization: Let Xe=V, Xtemp= Ф, B=Xe

Step 4-1.For (V, U1),

If T(U1)T(V), then D=V-max(V)U1, W(r)=f(D(r)),

r=18(W(r)|{p|ptrT(U1)}|)E3
=3.

Then add V+U1, V+2U1, V+3U1 to the set of Xtemp,

Therefore, Xtemp={V+U1, V+2U1, V+3U1}

Step 5-1.If Xtemp≠Φ, then let B=Xtemp={V+U1, V+2U1, V+3U1}

Xe=XeB={V, V+U1, V+2U1, V+3U1}, Xtemp=Φ.

Go to Step4 in Algorithm 1.

Step 4-2.For any pair of (Bi, U1), T(U1)T(Bi) is satisfied. Therefore, Xtemp

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

As a result of above sequence, Md is reachable from M0. The firing sequence is t5*t1*t2*t6*t7*t3*t4*t8. Its firing count vector corresponds to V+U1=(1,1,1,1,1,1,1,1) in the sufficient test space Xe. This example shows that suppressing Bi+kUj (k=1) in Xe may eliminate some possible executable solution.

Example 2. Consider the PN of Figure 2, given the initial marking M0=(1,0,0,0,0,0,0,0,1,0) and the destination marking Md=(0,0,0,1,0,0,0,0,1,0), calculate the sufficient test space Xe.

Figure 1.

Petri net structure

Figure 2.

Petri net structure

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

  2. Solve the equation AX=Md-M0, 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=(1,1,1,0,0,0,0,1,0,0)+k1(0,0,0,1,1,1,1,0,0,0)+k2(0,0,0,0,0,0,0,0,1,1)E4

k1 and k2 are nonnegative integer.

  1. Initialization: Let Xe=V, Xtemp=Φ, B=Xe

Step 4-1. For (V, U1),

If T(U1)T(V), then D=V-max(V)U1, W(r)=f(D(r)),

r=110(W(r)|{p|ptrT(U1)}|)E5
=2.

Then add V+U1, V+2U1 to Xtemp. So Xtemp={V+U1, V+2U1}

For (V, U2),

If T(U2)T(V), then D=V-max(V)U2, W(r)=f(D(r)),

r=110(W(r)|{p|ptrT(U2)}|)E6
=1.

Then add V+U2 to Xtemp. So Xtemp={V+U1, V+2U1, V+U2}

Step 5-1. If Xtemp≠Φ, then let B=Xtemp={V+U1, V+2U1, V+U2},

Xe=XeB={V, V+U1, V+2U1, V+U2}. Let’s put Xtemp=Φ.

Go to Step 4 in Algorithm 1.

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

For (V+U1, U2),

If T(U2)T(V+U1), then D1=(V+U1)-max(V+U1)U2, W1(r)=f(D1(r)),

r=110(W1(r)|{p|ptrT(U2)}|)E7

=2

.

Then add V+U1+U2 and V+U1+2U2 to Xtemp. So Xtemp={V+U1+U2, V+U1+2U2}

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

For (V+2U1, U2),

If T(U2)T(V+2U1), then D2=(V+2U1)-max(V+2U1)U2, W2(r)=f(D2(r)),

r=110(W2)(r)|{p|ptrT(U2)}|)E8

=3.

Then add V+2U1+U2, V+2U1+2U2, and V+2U1+3U2 to Xtemp. So Xtemp={V+U1+U2, V+U1+2U2, V+2U1+U2, V+2U1+2U2, V+2U1+3U2}

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

For (V+U2, U1),

If T(U1)T(V+U2), then D3=(V+U2)-max(V+U2)U1, W3(r)=f(D3(r)),

r=110(W3(r)|{p|ptrT(U1)}|)E9

=3.

Then add V+U2+U1, V+U2+2U1, and V+U2+3U1 to Xtemp. So Xtemp={V+U1+U2, V+U1+2U2, V+2U1+U2, V+2U1+2U2, V+2U1+3U2, V+U2+3U1}

Step 5-2.If Xtemp≠Φ, then let B=Xtemp={V+U1+U2, V+U1+2U2, V+2U1+U2, V+2U1+2U2, V+2U1+3U2, V+U2+3U1}.

So, Xe=Xe+B={V, V+U1, V+2U1, V+U2, V+U1+U2, V+U1+2U2, V+2U1+U2, V+2U1+2U2, V+2U1+3U2, V+U2+3U1}. Let’s put Xtemp=Φ.

Go to Step 4 in Algorithm 1.

Step 4-3.For any pair of (Bi, Uj), because T(Uj) T(Bi), Xtemp

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

Md is reachable from M0. The firing sequence is t9*t7*t4*t1*t5*t6*t7*t2*t4*t5*t6*t10*t3*t8. Its firing count vector corresponds to V+2U1+U2=(1,1,1,2,2,2,2,1,1,1) in the sufficient test space Xe. This example illustrates that suppressing Bi+kUj (k=β) in Xe may eliminate some possible executable solution.

4. Search of a firing sequence

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

Definition 12. Let S= t1t2…tr be a finite transition sequence. The transitions appearing in S are defined by the set Z(S) ={t1, t2, …, tr}. 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(Xei) under M0

  1. According to I, determine all the conflict structure Ci=<p, Tci>, and construct Tc and C.

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

  3. Under M and X, calculate F=Fo+Fc from Definition 6.

If Fo≠0, go to Step 4.

If Fo =0 and Fc≠0, go to Step 5.

If F=0, go to step 6.

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

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

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

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

Let M=M’, X=Xe[tj], S=S*tj.Go to Step 3

Step 6. If X=0, then Md is reachable from M0 and S=S(Xei) is one of the firing sequences, end. Otherwise, go to Step 7.

  1. If all the branches in Step 5 have been implemented, then Md 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=Md-M0. The actual firing vector F=Fo+Fc is obtained with M and X. Let to∈T(Fo) and tc∈T(Fc).

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

Case 2: If Fo=0 and Fc≠0, then the firing of each transition in S(Fc) 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 Fo=0 and Fc=0, then no transition is enabled.

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

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

Proof:

  1. Let T(Fo)={to1, to2, …, ton}. For a transition to1∈T(Fo), σ can be represented as σ =σ1*to2, where to1Z(σ1). Then M0σ1M1to1M2σ2Md is a firing sequence. Since T(Fo) is the set of transitions possible to be enabled under M0, M0 enables to1. Therefore it is possible to put M0to1M3. By the definition of Fo, we have M3(p)≥M0(p) for any p∈Z(σ1). So σ1 is enabled under M3 because σ1 is enabled under M0 (Monotonicity Lemma). After σ1 firing, M2 is reachable from M3. Therefore, we have M0to1M3σ1M2. Since σ2 is enabled under M2, to112 is a firing sequence under M0.

  2. Under M3, let’s consider the new T(Fo)={to2, …, ton}T(Fo’), where T(Fo’) is the set of transition generated after to1 firing and may be empty. For a transition to2∈T(Fo), σ12 can be represented as σ123*to24, where to2Z(σ3). Then σ3*to24 is a firing sequence. By the same way described in Step 1, we can prove that to234 is a firing sequence under M3.

  3. By Step 1 and Step 2, to1*to234 is a firing sequence under M0.

  4. In the same way, it is proven that to1*to2*…*tonij is a firing sequence under M0. According to the definition of Fo, all transitions in {to1, to2, …, ton} can fire simultaneously under M0. Let’s put σ’=σij, then (S(Fo)*σ’)∈S(X) is a firing sequence under M0.

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

Figure 3.

Petri net structure

  1. There are two conflict structures, C1=<p1, {t2, t5}>, C2=<p2, {t3, t4}>, Tc={t2, t3, t4, t5}.

  2. Initialization: M=M0= (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 t6 is 1-enabled. Then, Fo=(0,0,0,0,0,1,0).

  4. Fire S(Fo)= t6. Then the reachable marking M’ becomes (1,0,0,0,0,0,0,1,0)

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

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

Step 4-1.Fire S(Fo)=t7. Then, the reachable marking becomes M’=(1,0,0,0,0,0,1,0,1)

Let M=M’, X=X-Fo=(1,2,1,1,1,0,0), S=t6*t7. Go to Step 3 in Algorithm 2.

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

Step 4-2.Fire S(Fo)=t2 (t2 is not an effective conflict transition because t5 cannot enable),

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

Let M=M’, X=X-Fo=(1,1,1,1,1,0,0), S= t6*t7*t2. Go to Step 3 in Algorithm 2.

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

Step 4-3.Fire S(Fo)=t3 (t3 is not an effective conflict transition because t4 cannot enable),

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

Let M=M’, X=X-Fo=(1,1,0,1,1,0,0), S= t6*t7*t2*t3. 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, Md 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 M0=(1,0,0,0,0,0,0,0,1) in the PN of Figure 5, is the destination marking Md=(0,0,1,0,1,0,0,0,1) reachable from M0 ?

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=Md-M0, get the positive integer minimal particular solutions V1=(0,2,1,0,2,2,0,0), V2=(2,2,1,2,0,0,0,0) and V3=(1,2,1,1,1,1,0,0)

  3. Initialization: Let Xe={V1, V2, V3}, Xtemp=Φ, B=Xe

Step 4-1 For (V1, U),

Figure 4.

Firing path tree on reachability of Figure 3.

Figure 5.

Petri net structure

If T(U)T(V1), then D1=V1-max(V1)U, W1(r)=f(D1(r)),

r=18(W1(r)|{p|ptrT(U)}|)=2E10

Then add V1+U, V1+2U to Xtemp. Then, Xtemp={V1+U, V1+2U }

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

For (V3, U),

If T(U)T(V3), then D3=V3-max(V3)U, W3(r)=f(D3(r)),

r=18(W3(r)|{p|ptrT(U)}|)=1E11

Then add V3+U to Xtemp, Xtemp={V1+U, V1+2U, V3+U}

Step 5-1 If Xtemp≠Φ, then let B=Xtemp={V1+U, V1+2U, V3+U},

Xe=XeB={V1, V2, V3, V1+U, V1+2U, V3+U }. Let’s put Xtemp=Φ. Go to Step 4 in Algorithm 1.

  1. For any pair of (Bi, U), because T(Uj)T(Bi), Xtemp=Φ.

  2. If Xtemp=Φ, then end.

Consequently, the sufficient test space becomes Xe={V1, V2, V3, V1+U, V1+2U, V3+U}.

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

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

  1. For X=V1=(0,2,1,0,2,2,0,0)

The implementing process is shown in Figure 6.

  1. For X=V2=(2,2,1,2,0,0,0,0)

Carrying out the same process, the conclusion is as follows: Md is not reachable under V2.

  1. For X=V3=(1,2,1,1,1,1,0,0)

Carrying out the same process, the conclusion is as follows: Md is not reachable under V2.

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

Carrying out the same process shown in Figure 7, the conclusion is as follows: Md is reachable from M0 under V1+U. V1+U is an executable solution in Xe, and the firing sequence is t5*t7*t6*t2*t3*t5*t6*t2*t8.

As a result of calculating each element of the sufficient test space Xe={V1, V2, V3, V1+U, V1+2U, V3+U} individually, a firing sequence is finally found at the fourth element (V1+U) of Xe. Therefore, the elements V1+2U and V3+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 V1.

Figure 7.

Firing path tree for V1+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.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Gi Bum Lee, Han Zandong and Jin S. Lee (August 29th 2012). Reachability Criterion with Sufficient Test Space for Ordinary Petri Net, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/50518. Available from:

chapter statistics

979total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

A Forward On-The-Fly Approach in Controller Synthesis of Time Petri Nets

By Parisa Heidari and Hanifa Boucheneb

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us