On calculation of state space for linear system of simple sequential processes with resources

Abstract

This work focuses on the calculation of state space for linear system of simple sequential processes with resources (LS³PR). The method, different from reachability graphs rendering high computational complexity, finds reachable markings by combinatorics. First, the set of invariant markings can be obtained by combinatorics if the influence of deadlocks is ignored. Unfortunately, some of reachable states in the set of invariant markings are proved to be spurious if deadlocks exist. Second, we find the spurious markings by computing a set of minimal spurious markings, which can be calculated by a proposed algorithm based on strict minimal siphons. The obtained spurious markings are proved to cover all the spurious markings of the LS³PR. Removing the spurious markings from the set of invariant markings, the left ones constitute the state space of the LS³PR. The detailed method is shaped to an algorithm. The effectiveness of the algorithm is proved by example calculation and analysis. Finally, we analyze the computational complexity of the proposed method compared with reachability graphs.

Keywords

Flexible manufacturing system Petri net reachable marking siphon combinatorics

Introduction

Different kinds of products can be made in a flexible manufacturing system (FMS) by computer control based on the allocation of a limited number of shared resources. Due to the existence of competition for resources, deadlocks are always unavoidable. Petri nets, as a tool with powerful modeling and analysis abilities, are widely used in the deadlock prevention problems of resource allocation systems.^1,2 Petri nets–based deadlock prevention uses an offline computation mechanism to impose constraints on a system to prevent the system from reaching deadlock states.

Almost without exception, the existing literatures try to evaluate the performance of liveness-enforcing supervisors in terms of behavioral permissiveness, computational complexity, and structural complexity. Reachability graph (RG) analysis is an important technique for deadlock control, based on which an optimal or nearly optimal supervisor with high behavioral permissiveness can always be obtained. Depending on the calculation of state space, the theory of regions can definitely find an optimal liveness-enforcing supervisor if it exists.³ The theory of regions is used in previous studies^4–6 for an S³PR⁷ to obtain a suboptimal liveness-enforcing supervisor.

However, reachability analysis^8–10 needs a reachable marking enumeration, which requires a large number of consumptions of resources. In some cases, the analysis may stop due to the exhausted memory. It is shown in the work by Lipton¹¹ that the complexity of the reachability problem of a Petri net is exponential. Currently, using the popular integrated net analyzer (INA)¹² to obtain the state space of a large Petri net model is difficult, even impossible. Large sets of reachable markings with shared data structures can be represented by binary decision diagrams (BDDs). Besides, BDDs can implement efficient manipulation on the sets of reachable markings. In order to overcome the state explosion problem, BDD is used by Chen et al.¹³ to represent the state space. However, the method still requires a complete enumeration of reachable markings whose number increases exponentially with the size of a Petri net. Hence, state explosion problem is still a technique barrier of using RG analysis to prevent deadlocks in an FMS. Consequently, we figure out another way with relatively low computational complexity, different from RG, to handle state–space problem.

We tackle the problem in the previous work¹⁴ for arbitrary marked graphs by finding the number of reachable markings in an algebraic way. And the subsequent work^15,16 extends the research field from marked graphs to S³PR, where might exist deadlocks. It deals with an approximate calculation of the number of reachable markings of an S³PR to predict whether the number is beyond the upper limit of computing power.

Our previous works mainly focus on number estimation of reachable markings for deciding whether it is deserved to conduct an RG analysis. In this work, we place emphasis on the complete enumeration of reachable markings for a subclass of S³PR, called LS³PR. First, we find the set of invariant markings (IMs) of an LS³PR by combinatorics. Then, excluding all spurious markings from the set by finding a set of minimal spurious markings basing on strict minimal siphon (SMS), the left markings are the ones to be desired.

The article is organized as follows. Section “Preliminaries” presents the preliminaries used throughout this article. The detailed approach of computing the state space of an LS³PR is introduced and a well-known example of LS³PR is adopted to support the approach in section “Main approach.” We perform an analysis on computational complexity of the proposed method compared with RG in section “Computational complexity analysis and comparison.” Finally, the conclusion of the article is presented in section “Conclusion.”

Preliminaries

Petri nets

A Petri net is a four-tuple $N = (P, T, F, W)$ , where P and T are finite, nonempty, and disjoint sets. P is a set of places and T is a set of transitions. $F \subseteq (P \times T) \cup (T \times P)$ is called a flow relation, represented by arcs with arrows from places to transitions or from transitions to places. $W : (P \times T) \cup (T \times P) \to N$ is a mapping that assigns a weight to an arc: $W (x, y) > 0$ if $(x, y) \in F$ , where $x, y \in P \cup T$ and $N = {0, 1, 2, \dots}$ . If $W (x, y) \leq 1$ , $\forall (x, y) \in F$ , the net is called an ordinary Petri net, denoted by $N = (P, T, F)$ ; otherwise, it is called a generalized one. A subnet $N_{s} = (P_{s}, T_{s}, F_{s}, W_{s})$ of N is generated by $X = P_{s} \cup T_{s}$ , where $P_{s} = P \cap X$ , $T_{s} = T \cap X$ , $F_{s} = F \cap (X \times X)$ , and $\forall f \in F_{s}, W_{s} (f) = W (f)$ .

M is used to denote a marking or state of a Petri net N, which is a mapping from P to $N$ . The number of tokens in place p is denoted as $M (p)$ . For economy of space, multisets are used to describe markings and vectors. Hence, here, vector M is denoted as $\sum_{p \in P} M (p) \cdot p$ . $(N, M_{0})$ is called a net system, where $M_{0}$ is called an initial marking of N. $M^{S} = \sum_{p \in S} M^{S} (p) \cdot p$ is used to denote a marking of a subset, and $S \subseteq P$ is a mapping from S to $N$ and $M (S)$ is used to denote the sum of tokens in S. $M_{0}^{S}$ is called an initial marking of S such that $\forall p \in S$ , $M_{0}^{S} (p) = M_{0} (p)$ .

${}^{•}x = {y \in P \cup T | (y, x) \in F}$ and $x^{•} = {y \in P \cup T | (x, y) \in F}$ are used to denote the preset and postset of x, respectively. Similarly, given $X \subseteq P \cup T$ , ${}^{•}X = {\cup_{x \in X}}^{•} x$ , and $X^{•} = \cup_{x \in X} x^{•}$ . A nonempty set $S \subseteq P$ is called a SMS if there is no siphon contained in it and ${}^{•}S \subset \neq S^{•}$ .

A transition $t \in T$ is enabled at a marking M if $\forall p \in^{•} t, M (p) \geq W (p, t)$ . This fact is denoted as $M [t 〉$ . Firing it yields a new marking $M'$ such that $\forall p \in P$ , $M' (p) = M (p) - W (p, t) + W (t, p)$ as denoted by $M [t 〉 M'$ . $M'$ is called an immediately reachable marking from M and M is called a closely previous reachable marking of $M'$ . A marking $M ″$ is said to be reachable from M if there exists a sequence of transitions $σ = t_{0} t_{1} \dots t_{n}$ and markings $M_{1}, M_{2}, \dots, and M_{n}$ such that $M [t_{0} 〉 M_{1} [t_{1} 〉 M_{2} \dots M_{n} [t_{n} 〉 M ″$ holds. The set of markings reachable from M in N is called the reachability set of Petri net $(N, M)$ and denoted as $R (N, M)$ . $| R (N, M) |$ is used to denote the number of reachable markings in $R (N, M)$ . I is called a P-invariant if $\forall M \in N^{| P |}$ , $I^{T} M = I^{T} M_{0}$ . $I_{r} (N, M_{0}) = {M \in N^{∥ P ∥} | I_{r}^{T} M = I_{r}^{T} M_{0}}$ is called the set of IMs. A P-invariant I is called minimal P-semiflow if it is non-negative and its support $∥ I ∥ = {p | I (p) \neq 0}$ is not a superset of the support of any other P-invariants. Here, $\sum_{p \in ∥ I ∥} I (p) \cdot p$ is used to denote vector I.

Let I be a minimal P-semiflow. $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ is a marked subnet generated by $X = ∥ I ∥ \cup^{•} ∥ I ∥ \cup ∥ I ∥^{•}$ , where $N^{∥ I ∥} = (∥ I ∥,^{•} ∥ I ∥ \cup ∥ I ∥^{•}, F_{X}, W_{X})$ and $M_{0}^{∥ I ∥}$ is a mapping from $P_{I}$ to $N$ with $\sum_{p \in ∥ I ∥} M_{0} (p) • p$ as its multiset form. A P-vector of $N^{∥ I ∥}$ is a column vector $I_{Δ} : P_{I} \to Z$ indexed by $P_{I}$ , where $P_{I}$ denotes the set of places in $∥ I ∥$ . $I_{I_{Δ}} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) = {M \in N^{| P_{I} |} | I_{Δ}^{T} M = I_{Δ}^{T} M_{0}^{∥ I ∥}}$ denotes the set of IMs of $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ .

Let $I_{i}$ be a minimal P-semiflow of N and $I = \sum_{i = 1}^{n} I_{i}$ be a P-semiflow of N. $I_{Δ i}$ is a minimal P-semiflow of $N^{∥ I ∥}$ and $I_{Δ} = \sum_{i = 1}^{n} I_{Δ i}$ is a P-semiflow of $N^{∥ I ∥}$ . $I_{Δ}$ and $I_{Δ i}$ , $i \in {1, 2, \dots, n}$ , are column vectors: $P_{I} \to Z$ indexed by $P_{I}$ . Let $X_{I}$ be a matrix where each column is a minimal P-semiflow of $N^{∥ I ∥}$ . $I_{X_{I}} (N^{∥ I_{Δ} ∥}, M_{0}^{∥ I_{Δ} ∥}) = {M \in N^{| P_{I} |} | {X_{I}}^{T} M = {X_{I}}^{T} M_{0}^{I}}$ denotes the set of IMs of $(N^{∥ I_{Δ} ∥}, M_{0}^{∥ I_{Δ} ∥})$ .

Let X be a matrix where each column is a minimal P-semiflow of N and denote the set of IMs of $(N, M_{0})$ as $I_{X} (N, M_{0}) = {M \in N^{| P |} | X^{T} M = X^{T} M_{0}}$ . It is found that $I_{X_{I}} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) = I_{I_{Δ}} (N^{∥ I ∥}, M_{0}^{∥ I ∥})$ , if $n = 1$ , and $I_{X_{I}} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) = I_{X} (N, M_{0})$ if n denotes the number of all the minimal P-semiflows in N. The number of markings in $I_{I} (N^{∥ I ∥}, M_{0}^{∥ I ∥})$ is denoted as $| I_{I} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) |$ .

LS³PR

A class of Petri nets defined by Ezpeleta et al.,⁷ called LS³PR, is introduced in this subsection.

Definition 1

A simple sequential process, called S²P for short, is a Petri net $N = ({p^{0}} \cup P_{A}, T, F)$ such that (1) $P_{A} \neq \emptyset$ denotes the set of operation places; (2) $p^{0} \notin P_{A}$ denotes the idle process place; (3) N is a strongly connected state machine; and (4) every process of N contains idle place $p^{0}$ .⁷

Definition 2

A system of simple sequential process with resources, called S³PR for short, is a Petri net $N = ({p^{0}} \cup P_{A} \cup P_{R}, T, F)$ such that⁷

$P_{R} \neq \emptyset$ and $(P_{A} \cup {p^{0}}) \cap P_{R} = \emptyset$ ; $\forall p \in P_{A}$ , $\forall t \in^{•} p$ , $\forall t' \in p^{•}$ , $\exists r_{p} \in P_{R}$ , ${}^{•}t \cap P_{R} = t' • \cap P_{R} = {r_{p}}$ ; $\forall r \in P_{R}$ , ${}^{• •}r \cap P_{A} = r^{• •} \cap P_{A} \neq \emptyset$ ; $\forall r \in P_{R}$ , ${}^{•}r \cap r^{•} = \emptyset$ ; ${}^{• •}{(p^{0})} \cap P_{R} = (p^{0})^{• •} \cap P_{R} = \emptyset$ .

Let $N_{i} = ({p_{i}^{0}} \cup P_{A_{i}} \cup P_{R_{i}}, T_{i}, F_{i})$ , $i \in {1, 2}$ , be two S³PR with $(P_{A_{1}} \cup {p_{1}^{0}}) \cap (P_{A_{2}} \cup {p_{2}^{0}}) = \emptyset$ , $P_{R_{1}} \cap P_{R_{2}} = P_{C} \neq \emptyset$ , and $T_{1} \cap T_{2} = \emptyset$ . Then, the net $N = (P^{0} \cup P_{A} \cup P_{R}, T, F)$ composed by $N_{1}$ and $N_{2}$ via $P_{C}$ can be defined as follows: (1) $P_{A} = P_{A_{1}} \cup P_{A_{2}}$ , (2) $P^{0} = {p_{1}^{0}} \cup {p_{2}^{0}}$ , (3) $P_{R} = P_{R_{1}} \cup P_{R_{2}}$ , (4) $T = T_{1} \cup T_{2}$ , and (5) $F = F_{1} \cup F_{2}$ .

$P_{R}$ is called the set of resource places; for $r \in P_{R}$ , $H (r) =^{• •} r \cap P_{A}$ is called the set of holders of r.

Definition 3

A linear S³PR, called LS³PR for short, is an ordinary Petri net $N = (P^{0} \cup P_{A} \cup P_{R}, T, F)$ such that⁷

$\forall i \in {1, \dots, l}$ , the subnet $N_{i}$ generated by ${p_{i}^{0}} \cup P_{A_{i}} \cup T_{i}$ is a strongly connected state machine, such that every cycle contains place $p_{i}^{0}$ and $\forall p \in P_{A_{i}}, | p^{•} | = 1$ .

$\forall i \in {1, \dots, l}, \forall p \in P_{A_{i}},^{• •} p \cap P_{R} = p^{• •} \cap P_{R}$ and $|^{• •} p \cap P_{R} | = 1$ .

N is strongly connected.

Property 1

Let $N = O_{i = 1}^{n} N_{i} = (P^{0} \cup P_{A} \cup P_{R}, T, F)$ be an LS³PR consisting of n simple sequential processes and S be a siphon in N:⁷

Any $p \in P_{A_{i}}$ with $I_{p}$ as its associated minimal P-semiflow, $∥ I_{p} ∥ = P_{A_{i}} \cup {p_{i}^{0}}$ .

Any resource $r \in P_{R}$ with $I_{r}$ as its associated minimal P-semiflow, $∥ I_{r} ∥ = {r} \cup H (r)$ .

$\forall p \in [S]$ , $\exists r \in S^{R}$ , $p \in H (r)$ and $\forall r' \in P_{R} \ {r}$ , $p \notin H (r')$ .

$[S] \cup S$ is the support of a P-semiflow of N.

$[S] = \cup_{i = 1}^{n} [S]^{i}$ , where $[S]^{i} = [S] \cap P_{A_{i}}$ .

Definition 4

A Petri net $(N, M_{0})$ is quasi-safe if $\forall M \in R (N, M_{0})$ , $\forall p \in P_{A} \cup P_{R}$ , $M (p) \leq 1$ .

In this article, quasi-safe LS³PRs are the subclass of Petri nets we focus on enumerating the reachable markings.

Main approach

This section aims to elaborate on how to completely enumerate the reachable markings of an LS³PR. First, for clarity, we use a simple example to exhibit the rough calculation of reachable markings by the proposed method. Second, the set of IMs of an LS³PR, obtained in the case of ignoring deadlocks, can be calculated by combinatorics. In the following subsection, we exclude all spurious markings from the set and obtain the reachable markings of the LS³PR. Finally, we give an algorithm as well as a supporting example to shape the detailed approach.

A simple example

For the simple LS³PR in Figure 1, there are two P-invariants, $I_{1} = p_{2} + p_{6} + p_{7}$ and $I_{1} = p_{3} + p_{5} + p_{8}$ , containing resources. Supposing that there exists no deadlock, according to the definition of P-invariant, the tokens stayed in resource place initially can flow freely in the support of the P-invariant. For instance, we can consider that the token in $p_{7}$ can flow among $p_{2}$ , $p_{6}$ , and $p_{7}$ freely. Without considering deadlocks, by combinatorics, we can list the IM of the LS³PR, as shown in Table 1.

Figure 1.

A simple LS³PR.

Table 1.

Invariant markings of the LS³PR in Figure 1.

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$
$M_{1}$	2	0	0	2	0	0	1	1
$M_{2}$	1	1	0	2	0	0	0	1
$M_{3}$	2	0	0	1	0	1	0	1
$M_{4}$	1	0	1	2	0	0	1	0
$M_{5}$	0	1	1	2	0	0	0	0
$M_{6}$	1	0	1	1	0	1	0	0
$M_{7}$	2	0	0	1	1	0	1	0
$M_{8}$	1	1	0	1	1	0	0	0
$M_{9}$	2	0	0	0	1	1	0	0

We know that the markings in Table 1 are the reachable markings of the LS³PR if there exists no deadlock. Unfortunately, by reachability analysis, $M_{6}$ is proved spurious and should be removed. Hence, the reachable markings of the LS³PR in Figure 1 are obtained and shown in Table 2.

Table 2.

Reachable markings of the LS³PR in Figure 1.

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$
$M_{1}$	2	0	0	2	0	0	1	1
$M_{2}$	1	1	0	2	0	0	0	1
$M_{3}$	2	0	0	1	0	1	0	1
$M_{4}$	1	0	1	2	0	0	1	0
$M_{5}$	0	1	1	2	0	0	0	0
$M_{7}$	2	0	0	1	1	0	1	0
$M_{8}$	1	1	0	1	1	0	0	0
$M_{9}$	2	0	0	0	1	1	0	0

Thus, in this article, we place an emphasis on how to steer clear of RG to find the state space of an LS³PR.

IMs

In this study, first, we construct a state space of an LS³PR based on P-invariants. According to the definition of P-invariants, the space can be obtained by combinatorics. In this work, P_r-semiflow is used to denote a P-semiflow with resources.

Theorem 1

The number of combinations of placing m elements into n distinguishable containers is $C (n + m - 1, m) = (n + m - 1)! / [m! (n - 1)!]$ .¹⁷

Corollary 1

Let $(N, M_{0})$ be an LS³PR, $I_{r}$ be a minimal P_r-semiflow with $∥ I_{r} ∥ = {r} \cup H (r)$ , and $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ be a marked subnet of $(N, M_{0})$ supported by I. Supposing that there are m places in $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ , the number of IMs of $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ is $| I_{I_{Δ}} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) | = C (m + 1 - 1, 1) = m$ .

By Corollary 1, we find the number of IMs of $(N^{∥ I ∥}, M_{0}^{∥ I ∥})$ and each IM in $I_{I} (N^{∥ I ∥}, M_{0}^{∥ I ∥})$ can be generated by combinatorics. In an LS³PR, $∥ I_{r} ∥ = {r} \cup H (r)$ and $M (∥ I_{r} ∥) = 1$ . The token in $∥ I_{r} ∥$ can flow freely among the places in $∥ I_{r} ∥$ if we do not consider deadlocks.

$I_{p_{7}} = [0, 1, 0, 0, 0, 1, 1, 0]^{T}$ and $I_{Δ} = [1, 1, 1]^{T}$ . The net $(N^{∥ I_{p_{7}} ∥}, M_{0}^{∥ I_{p_{7}} ∥})$ shown in Figure 2, supported by $I_{p_{7}}$ , is a marked subnet of the LS³PR in Figure 1. $I_{p_{7}} = p_{2} + p_{6} + p_{7}$ and $M_{0}^{I_{p_{7}}} = p_{7}$ . $p_{7}$ has two holders $p_{2}$ and $p_{6}$ . The token in $p_{7}$ can flow freely among $p_{2}$ , $p_{6}$ , and $p_{7}$ . By Corollary 1, we find $| I_{I_{Δ}} (N^{∥ I ∥}, M_{0}^{∥ I ∥}) | = 3$ , and the specific markings are generated and shown in Table 3.

Figure 2.

A subnet of an LS³PR.

Table 3.

Markings in $I_{I_{Δ}} (N^{∥ I ∥}, M_{0}^{∥ I ∥})$ .

$∥ I_{p_{3}} ∥$	$p_{1}$	$p_{2}$	$p_{3}$
$M_{1}$	1	0	0
$M_{2}$	0	1	0
$M_{3}$	0	0	1

Definition 5

Let $∥ I_{r_{1}} ∥$ , $∥ I_{r_{2}} ∥$ , …, and $∥ I_{r_{n}} ∥$ be supports of minimal P_r-semiflows in $(N, M_{0})$ and $M_{0}^{∥ I_{r_{1}} ∥}$ , $M_{0}^{∥ I_{r_{2}} ∥}$ , …, and $M_{0}^{∥ I_{r_{n}} ∥}$ be the initial states of $∥ I_{r_{1}} ∥$ , $∥ I_{r_{2}} ∥$ , …, and $∥ I_{r_{n}} ∥$ , respectively. A set $G = \cup_{i = 1}^{m} ∥ I_{r_{i}} ∥$ is called an m-configuration, where $m = | P_{R} \cap G |$ and $m \leq n$ . $M_{0}^{G} = \sum_{i = 1}^{m} M_{0}^{∥ I_{r_{i}} ∥}$ is the initial state of G.

In this article, suppose that the tokens in any minimal P_r-semiflow of an LS³PR stay in the resources originally. If ignoring deadlocks, the reachable states of $(N^{G}, M_{0}^{G})$ can be generated by combinatorics. The set of the states is called the set of reachable states of theory permissive of $(N^{G}, M_{0}^{G})$ , denoted as $R_{B} (N^{G}, M_{0}^{G})$ .

Property 2

By the multiplication rule of combinatorics, the least upper bound of the reachable states of an LS³PR $(N, M_{0})$ is $| R_{B} (N, M_{0}) | = Π_{r \in P_{R}} | R (N^{∥ I_{r} ∥}, M_{0}^{∥ I_{r} ∥}) |$ , where $I_{r}$ denotes any P_r-semiflow contained in the LS³PR.

Property 3

Let $M_{0}$ be the initial state of an LS³PR $(N, M_{0})$ , $p_{i}^{0}$ be the idle place of process i, and $P_{A_{i}}$ be the set of operation places of process i, then $\forall M \in R (N, M_{0})$ , $M (p_{i}^{0}) = M_{0} (p_{i}^{0}) - M (P_{A_{i}})$ .

By Property 2, the states in upper bound can be generated. Here is an example. There are two minimal P_r-semiflows in the LS³PR $(N, M_{0})$ shown in Figure 1. $I_{p_{7}} = p_{2} + p_{6} + p_{7}$ and $I_{p_{8}} = p_{3} + p_{5} + p_{8}$ . The reachable states of $∥ I_{p_{7}} ∥$ and $∥ I_{p_{8}} ∥$ are shown in Table 4.

Table 4.

States in $R (N^{∥ I_{p_{7}} ∥}, M_{0}^{∥ I_{p_{7}} ∥})$ and $R (N^{∥ I_{p_{8}} ∥}, M_{0}^{∥ I_{p_{8}} ∥})$ .

$∥ I_{p_{7}} ∥$	$p_{2}$	$p_{6}$	$p_{7}$	$∥ I_{p_{8}} ∥$	$p_{3}$	$p_{5}$	$p_{8}$
$M_{1}$	1	0	0	$M_{1}$	1	0	0
$M_{2}$	0	1	0	$M_{2}$	0	1	0
$M_{3}$	0	0	1	$M_{3}$	0	0	1

View $∥ I_{p_{7}} ∥$ and $∥ I_{p_{8}} ∥$ as a whole, denoted as G. That is to say, $G = ∥ I_{p_{7}} ∥ \cup ∥ I_{p_{8}} ∥$ . Combining the states in $R (N^{∥ I_{p_{7}} ∥}, M_{0}^{∥ I_{p_{7}} ∥})$ and $R (N^{∥ I_{p_{8}} ∥}, M_{0}^{∥ I_{p_{8}} ∥})$ , we have the reachable states of theory permissive of $(G, M_{0}^{G})$ and are show in Table 5.

Table 5.

Reachable states of theory permissive of $(N^{G}, M_{0}^{G})$ .

G	$p_{2}$	$p_{3}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$
$M_{1}$	1	1	0	0	0	0
$M_{2}$	1	0	1	0	0	0
$M_{3}$	1	0	0	0	0	1
$M_{4}$	0	1	0	1	0	0
$M_{5}$	0	0	1	1	0	0
$M_{6}$	0	0	0	1	0	1
$M_{7}$	0	1	0	0	1	0
$M_{8}$	0	0	1	0	1	0
$M_{9}$	0	0	0	0	1	1

Finally, considering idle places, by Property 3, we find the reachable states of theory permissive of $(N, M_{0})$ in Figure 1, as shown in Table 6.

Table 6.

Reachable states of theory permissive of $(N, M_{0})$ in Figure 1.

N	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$
$M_{1}$	0	1	1	2	0	0	0	0
$M_{2}$	1	1	0	1	1	0	0	0
$M_{3}$	1	1	0	2	0	0	0	1
$M_{4}$	1	0	1	1	0	1	0	0
$M_{5}$	2	0	0	0	1	1	0	0
$M_{6}$	2	0	0	1	0	1	0	1
$M_{7}$	1	0	1	2	0	0	1	0
$M_{8}$	2	0	0	1	1	0	1	0
$M_{9}$	2	0	0	2	0	0	1	1

Unreachable states exclusion

Without deadlocks, the tokens in the P_r-semiflows of an LS³PR can flow freely among the places in the support of the P_r-semiflow. The existence of deadlocks makes part of states unreachable. It is proved in the work by Ezpeleta et al.⁷ that an SMS means at least a deadlock. Hence, we concentrate on an SMS-based method to determine the unreachable states from the upper bound.

Let $R_{B} (N, M_{0})$ and $R (N, M_{0})$ denote the set of reachable states of theory permissive and the set of reachable states of an LS³PR $(N, M_{0})$ , respectively. Here, $R_{U} (N, M_{0}) = {M | M \in R_{B} (N, M_{0}) \land M \notin R (N, M_{0})}$ is used to denote the set of unreachable states.

Definition 6

Let G be an m-configuration of an LS³PR and $G = ∥ I_{r_{1}} ∥ \cup ∥ I_{r_{2}} ∥ \cup \dots \cup ∥ I_{r_{m}} ∥$ . Supposing that there exists an SMS S that satisfies $G = S \cup [S]$ , then G is denoted an m-*configuration. Sometimes, m-*configuration is denoted as *configuration for short.

Theorem 2

Let $G = ∥ I_{r_{1}} ∥ \cup ∥ I_{r_{2}} ∥ \cup \dots \cup ∥ I_{r_{m}} ∥$ be an m-*configuration of an LS³PR $(N, M_{0})$ . Suppose that $p_{1} \in ∥ I_{r_{1}} ∥ \cap P_{A}$ , $p_{2} \in ∥ I_{r_{2}} ∥ \cap P_{A}$ , …, $p_{m} \in ∥ I_{r_{m}} ∥ \cap P_{A}$ . $M_{u}^{G} = p_{1} + p_{2} + \dots + p_{m}$ is an unreachable state of $(N^{G}, M_{0}^{G})$ if $\forall p_{i} \in {p_{1}, p_{2}, \dots, p_{m}}$ , $\forall p_{j} \in^{• •} p_{i} \cap P_{A}$ , $p_{j} \in G$ .

Proof

We prove it by contradiction. If $M_{u}^{G}$ is reachable, let $M_{P} = {M | M = M_{u}^{G} - p_{i} + p_{j_{1}} + \dots + p_{j_{k}} + r_{i}, p_{i} \in {p_{1}, p_{2}, \dots, p_{m}}, k \geq 1}$ be the set of closely previous states of $M_{u}^{G}$ in $R (N^{G}, M_{0}^{G})$ , where $p_{j_{1}}, \dots, p_{j_{k}} \in^{• •} p_{i} \cap P_{A}$ and $r_{i} \in^{• •} p_{i} \cap P_{R}$ . Supposing that $p_{j_{i}} \in ∥ I_{r_{j_{i}}} ∥$ , it is found that, $\forall M \in M_{P}$ , there exists p such that $p \neq p_{j_{i}}$ , $p \in ∥ I_{r_{j_{i}}} ∥$ , and $M (p) = 1$ . At this moment, there are two tokens in $∥ I_{r_{j_{i}}} ∥$ since $M (p) = 1$ and $M (p_{j_{i}}) = 1$ . It contradicts with the fact that $I_{r_{j_{i}}}$ is a P_r-semiflow. Hence, $M_{u}^{G}$ is an unreachable state of $(N^{G}, M_{0}^{G})$ .

Definition 7

Let G be an m-*configuration of an LS³PR $(N, M_{0})$ and $M_{u}^{G} = p_{1} + p_{2} + \dots + p_{m}$ be an unreachable state of $(N^{G}, M_{0}^{G})$ . $M_{u}^{G}$ is called a minimal unreachable state (MUS) of $(N^{G}, M_{0}^{G})$ if $\forall p_{i} \in {p_{1}, p_{2}, \dots, p_{m}}$ , $M = M_{u}^{G} - p_{i}$ is not an unreachable state of $(N^{G'}, M_{0}^{G'})$ , where $G' = {p | p \in G, p \notin | | I_{r_{i}} | |}$ and $I_{r_{i}}$ denotes the minimal P_r-semiflow where $p_{i}$ stays.

Property 4

Let $G = ∥ I_{r_{1}} ∥ \cup ∥ I_{r_{2}} ∥ \cup \dots \cup ∥ I_{r_{i}} ∥ \cup \dots \cup ∥ I_{r_{m}} ∥$ be an m-*configuration of an LS³PR $(N, M_{0})$ . G is at an unreachable state if $G' = {p | p \in G, p \notin ∥ I_{r_{i}} ∥}$ is at an unreachable state.

The net $N_{s}$ shown in Figure 3(a) is a subnet of the LS³PR in Figure 1. $| | I_{p_{7}} | |$ and $| | I_{p_{8}} | |$ make up a two-*configuration, denoted as $G = | | I_{p_{7}} | | \cup | | I_{p_{8}} | | = {p_{2}, p_{3}, p_{5}, p_{6}, p_{7}, p_{8}}$ . There exists an SMS $S = {p_{3}, p_{6}, p_{7}, p_{8}}$ in G. $M_{0}^{G} = p_{7} + p_{8}$ is the initial state of $N_{s}$ . By Theorem 2, it is concluded that $M_{u}^{G} = p_{3} + p_{6}$ is an unreachable state of $(N^{G}, M_{0}^{G})$ .

Figure 3.

(a) A subnet $N_{s}$ at an initial state and (b) an unreachable state.

As known to all, the unreachable states of an LS³PR are generated due to the existence of deadlocks. Precisely, deadlocks render part of states unreachable. By Property 4, we can find that the unreachable states of an LS³PR $(N, M_{0})$ can be derived from the MUS of the *configurations in $(N, M_{0})$ . If we can find all the MUSs, we can obtain all the unreachable states of $(N, M_{0})$ correspondingly.

Lemma 1

Let $G = ∥ I_{r_{1}} ∥ \cup ∥ I_{r_{2}} ∥ \cup \dots \cup ∥ I_{r_{i}} ∥ \cup \dots \cup ∥ I_{r_{m}} ∥$ be an m-*configuration of an LS³PR $(N, M_{0})$ . Suppose that $p_{1} \in ∥ I_{r_{1}} ∥ \cap P_{A}$ , $p_{2} \in ∥ I_{r_{2}} ∥ \cap P_{A}$ , …, $p_{i} \in ∥ I_{r_{i}} ∥ \cap P_{A}$ , …, $p_{m} \in ∥ I_{r_{m}} ∥ \cap P_{A}$ . $M^{G} = p_{1} + p_{2} + \dots + p_{i} + \dots + p_{m}$ is a reachable state of $(N^{G}, M_{0}^{G})$ if $M^{G} - p_{i}$ is a reachable state of $(N^{G'}, M_{0}^{G'})$ and $\exists p \in^{• •} p_{i} \cap P_{A}$ , $p \notin G$ , where $G' = {p' | p' \in G, p' \notin | | I_{r_{i}} | |}$ and $I_{r_{i}}$ denotes the minimal P_r-semiflow where $p_{i}$ stays.

Proof

An m-*configuration, as an independent part of N, and its reachable states are independent of that of other parts. If $M^{G} - p_{i}$ is a reachable state of $(N^{G'}, M_{0}^{G'})$ , we just need to check whether $p_{i}$ can be marked. If $p_{i}$ can be marked, then we can affirm that $M^{G}$ is reachable. We find there exists $p \in^{• •} p_{i} \cap P_{A}$ , $p \notin G$ implying that whether p can be marked does not depend on G. Hence, $p_{i}$ can be marked and $M^{G}$ is a reachable state of $(N^{G}, M_{0}^{G})$ .

Theorem 3

Algorithm 1 completely enumerates the MUS of the *configurations in an LS³PR $(N, M_{0})$ .

Algorithm 1. Computing the set of MUS of the *configurations in $(N, M_{0})$ .
Input: An L $S^{3}$ PR $(N, M_{0})$ and $Π$ . \* $Π$ denotes the set of all SMSs*\
Output: $U_{\min} .$ \* $U_{\min}$ denotes the set of all MUSs*\
$U min : = ϕ; : = 2 .$
while $Π \neq \emptyset$ ,
find the set of all SMSs with i resources from $Π$ , denoted as $S_{T}$ ,
foreach $S \in S_{T}$ ,
$S_{T} : = S_{T} \ S; Π : = Π \ S$ ,
construct an i-*configuration $G = \cup_{j = 1}^{i} \| \| I_{r_{j}} \| \|$ .
find the set of all unreachable states of $(N^{G}, M_{0}^{G})$ by the method in
Theorem 2, denoted as $U^{G}$ ,
foreach $M_{u}^{G} \in U^{G}$ ,
if $0 = ∄ M \in U_{m i n}$ such that $\forall p \in M$ , $M (p) = = M_{u}^{G} (p)$ .
$U_{\min} : = U_{\min} \cup {M_{u}^{G}}$ ,
end
end
end
$i : = i + 1$ ,
end
output $U_{\min}$ .

Proof

Without considering deadlocks, we can find a set of all the reachable states of theory permissive, denoted as $R_{G}$ . Actually, $R_{G}$ contains two parts: set of reachable states $R_{R}$ and set of unreachable states $R_{U}$ . By the theory of resource circuit, operation places in G can be divided into two parts: $P_{I} = {p | p \in G \cap P_{A}, \forall p' \in^{• •} p \cap P_{A}, p' \in G}$ and $P_{O} = {p | p \in G \cap P_{A}, \exists p' \in^{• •} p \cap P_{A}, p' \notin G}$ . For $\forall M \in R_{G}$ , $M = p_{1} + p_{2} + \dots + p_{i} + \dots + p_{m}$ and $K = {p_{1}, p_{2}, \dots, p_{i}, \dots, p_{m}}$ . Supposing that $\forall p \in K, p \in P_{I}$ , by Theorem 2, M is confirmed to be unreachable. Suppose that there is one place belonging to $P_{O}$ and the other places ( $P_{D}$ is the set of the other places) belonging to $P_{I}$ in K. If $M' = \sum_{p \in P_{D}} p$ is an unreachable state, by Property 4, M is confirmed to be unreachable; else by Lemma 1, M is confirmed to be reachable. Suppose that there are two place belonging to $P_{O}$ and the other places ( $P_{D}$ is the set of the other places) belonging to $P_{I}$ in K. If $M' = \sum_{p \in P_{D}} p$ is an unreachable state, by Property 4, M is confirmed to be unreachable; else by Lemma 1, M is confirmed to be reachable. By parity of reasoning, we can classify all the states in $R_{G}$ into $R_{R}$ and $R_{U}$ . Thus, it is noticed that the state in $R_{G}$ either satisfies the condition in Theorem 2 and Property 4 or Lemma 1. Furthermore, Property 4 is based on Theorem 2. Hence, in this sense, we can find all the unreachable state of $(N^{G}, M_{0}^{G})$ by Theorem 2. However, by Property 4, it is found that not all the unreachable states of a *configuration G obtained by Theorem 2 are a minimal one of $(N^{G}, M_{0}^{G})$ . Algorithm 1 reserves the unreachable states that are minimal. Hence, Algorithm 1 completely enumerates the MUS of the *configurations in $(N, M_{0})$ .

Definition 8

Let $G_{j}$ be a *configuration of an LS³PR $(N, M_{0})$ , $M_{ui}^{G_{j}}$ be one of MUSs of $(G_{j}, M_{0}^{G_{j}})$ , and $U_{\min}$ be the set of all the MUSs of the *configurations in $(N, M_{0})$ . The unreachable state in $R_{B} (N, M_{0})$ that satisfies $\forall p \in G, M_{ui}^{G_{j}} (p) = M (p)$ is called the unreachable state of $(N, M_{0})$ derived from $M_{ui}^{G_{j}}$ . The set of the unreachable states is denoted as $R_{ui}^{G_{j}} (N, M_{0})$ . $R_{U} (N, M_{0}) = \cup_{M_{ui}^{G_{j}} \in U_{\min}} R_{ui}^{G_{j}} (N, M_{0})$ denotes the set of all the unreachable states of $(N, M_{0})$ .

$R_{U} (N, M_{0})$ is the set of all the unreachable states of $(N, M_{0})$ . As previously mentioned, $R_{B} (N, M_{0})$ is the set of reachable states of $(N, M_{0})$ obtained without considering deadlocks. Hence, we just need to exclude the states in $R_{U} (N, M_{0})$ from $R_{B} (N, M_{0})$ and the left states are the desired ones. That is to say, $R (N, M_{0}) = {M | M \in R_{B} (N, M_{0}) \land M \notin R_{U} (N, M_{0})}$ is the set of the reachable states of $(N, M_{0})$ .

State estimate algorithm and example

We shape the detailed approach of calculating the state space of an LS³PR $(N, M_{0})$ to an algorithm and support it with an example in this section. First, a set of all the reachable states of theory permissive is generated by combinatorics. Then, we exclude the unreachable states by finding all the MUSs of the *configurations in $(N, M_{0})$ if there exist deadlocks. Finally, the left states are the reachable states of $(N, M_{0})$ .

Here, the LS³PR $(N, M_{0})$ in Figure 4, quoted from the literature,¹⁸ is taken as an example. According to the combinatorics and Property 2, we can find the set of reachable states of theory permissive $R_{B} (N, M_{0})$ . The states are listed in Table 7 (for economy of space, only a part of states is listed).

Figure 4.

A typical example.

Table 7.

States in $R_{B} (N, M_{0})$ .

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$	$p_{9}$	$p_{10}$	$p_{11}$	$p_{12}$	$p_{13}$	$p_{14}$	$p_{15}$	$p_{16}$
$M_{1}$	4	0	0	0	0	4	0	0	0	0	0	0	1	1	1	1
$M_{2}$	3	1	0	0	0	4	0	0	0	0	0	0	0	1	1	1
$M_{3}$	4	0	0	0	0	3	0	0	0	0	0	1	0	1	1	1
$M_{4}$	3	0	1	0	0	3	0	0	0	0	0	1	0	0	1	1
⋮			⋮
$M_{144}$	4	0	0	0	0	0	1	0	0	1	1	1	0	0	0	0

There are four SMSs, $Π = {S_{1}, S_{2}, S_{3}, S_{4}}$ , shown as follows

\begin{matrix} S_{1} = {p_{4}, p_{11}, p_{14}, p_{15}} \\ S_{2} = {p_{4}, p_{12}, p_{13}, p_{14}, p_{15}} \\ S_{3} = {p_{5}, p_{11}, p_{14}, p_{15}, p_{16}} \\ S_{4} = {p_{5}, p_{12}, p_{13}, p_{14}, p_{15}, p_{16}} \end{matrix}

Algorithm 2. Computing the reachability set of an LS³PR.
Input: An LS³PR $(N, M_{0})$ .
Output: $R (N, M_{0})$
$R_{U} (N, M_{0}) : = \emptyset$ ; $R (N, M_{0}) : = \emptyset$
find $R_{B} (N, M_{0})$ by Property 2.
compute the set of all the SMSs in N, denoted as $Π$ .
if $Π = = \emptyset$
$R (N, M_{0}) : = R_{B} (N, M_{0}) .$
else
apply Algorithm 1 to $Π$ to find $U_{\min}$ .
\* $U_{\min}$ denotes the set of all the MUSs of $the $ configurations in $(N, M_{0})$ \
foreach $M_{ui}^{G_{j}} (N, M_{0}) \in U_{\min}$ ,
compute $R_{ui}^{G_{j}} (N, M_{0})$ .
$R_{U} (N, M_{0}) : = R_{U} (N, M_{0}) \cup R_{ui}^{G_{j}} (N, M_{0})$ .
end
$R (N, M_{0}) : = R_{B} (N, M_{0}) \ R_{U} (N, M_{0})$ .
end
Output $R (N, M_{0})$ .

Based on the SMSs, four *configurations are constructed by Definition 6 and shown as follows

\begin{matrix} G_{1} = {p_{3}, p_{4}, p_{8}, p_{9}, p_{10}, p_{11}, p_{14}, p_{15}} \\ G_{2} = {p_{2}, p_{3}, p_{4}, p_{8}, p_{9}, p_{10}, p_{11}, p_{12}, p_{13}, p_{14}, p_{15}} \\ G_{3} = {p_{5}, p_{3}, p_{4}, p_{7}, p_{8}, p_{9}, p_{10}, p_{11}, p_{14}, p_{15}, p_{16}} \\ G_{4} = {p_{2}, p_{3}, p_{4}, p_{5}, p_{7}, p_{8}, p_{9}, p_{10}, p_{11}, p_{12}, p_{13}, p_{14}, p_{15}, p_{16}} \end{matrix}

By Theorem 2, we can find unreachable states of each *configuration. However, some of these states may be contained in the other *configurations that have less resources. Hence, it is necessary to find MUSs. By Definition 7, it is found that $M_{u_{1}}^{G_{1}} = p_{4} + p_{10}$ , $M_{u_{2}}^{G_{1}} = p_{9} + p_{10}$ , and $M_{u_{3}}^{G_{1}} = p_{10} + p_{11}$ are the MUSs of $M_{u}^{G_{1}}$ since $M = p_{i}, i \in {4, 10, 11}$ are not the MUSs of $M_{u}^{G_{1}}$ . There is no MUS in $N^{G_{4}}$ since the unreachable states of $N^{G_{4}}$ by Theorem 2 are not minimal. That is to say, the unreachable states derived from $M_{u}^{G_{4}}$ are included in the other unreachable states derived from $M_{u}^{G_{1}}$ , $M_{u}^{G_{2}}$ , or $M_{u}^{G_{3}}$ . For example, it is found that $M_{u_{1}}^{G_{1}} = p_{3} + p_{4} + p_{5} + p_{12}$ is an unreachable state but not MUS of $N^{G_{1}}$ since $M_{u_{1}}^{G_{2}} = p_{3} + p_{4} + p_{12}$ is an MUS. By applying Algorithm 1 to $Π$ , $U_{\min} = {M_{u_{1}}^{G_{1}}, M_{u_{2}}^{G_{1}}, M_{u_{3}}^{G_{1}}, M_{u_{1}}^{G_{2}}, M_{u_{2}}^{G_{2}}, M_{u_{3}}^{G_{2}}, M_{u_{1}}^{G_{3}}, M_{u_{2}}^{G_{3}}, M_{u_{3}}^{G_{3}}}$ is obtained and shown in Table 8.

Table 8.

MUS of *configurations.

$G_{i}$	MUS
$G_{1}$	$M_{u_{1}}^{G_{1}} = p_{4} + p_{10}$ ; $M_{u_{2}}^{G_{1}} = p_{9} + p_{10}$ ; $M_{u_{3}}^{G_{1}} = p_{10} + p_{11}$
$G_{2}$	$M_{u_{1}}^{G_{2}} = p_{3} + p_{4} + p_{12}$ ; $M_{u_{2}}^{G_{2}} = p_{3} + p_{9} + p_{12}$ ; $M_{u_{3}}^{G_{2}} = p_{3} + p_{11} + p_{12}$
$G_{3}$	$M_{u_{1}}^{G_{3}} = p_{4} + p_{5} + p_{8}$ ; $M_{u_{2}}^{G_{3}} = p_{5} + p_{8} + p_{9}$ ; $M_{u_{3}}^{G_{3}} = p_{5} + p_{8} + p_{11}$
$G_{4}$	$\emptyset$

MUS: minimal unreachable state.

In the following, we need to compute the unreachable states of $(N, M_{0})$ derived from the MUS in $U_{\min}$ . Taking $M_{u_{1}}^{G_{1}}$ as an example, we denote the unreachable states of $(N, M_{0})$ derived from $M_{u_{1}}^{G_{1}}$ as $R_{u_{1}}^{G_{1}} (N, M_{0})$ . The elements of $R_{u_{1}}^{G_{1}} (N, M_{0})$ are generated by Definition 8 and listed in Table 9.

Table 9.

States in $R_{u_{1}}^{G_{1}} (N, M_{0})$ .

	$p_{1}$	$p_{2}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{10}$	$p_{12}$	$p_{13}$	$p_{16}$
$M_{1}$	1	1	1	1	3	0	1	0	0	0
$M_{2}$	2	0	1	1	3	0	1	0	1	0
$M_{3}$	2	0	1	1	2	0	1	1	0	0
$M_{4}$	2	1	1	0	2	1	1	0	0	0
$M_{5}$	3	0	1	0	2	1	1	0	1	0
$M_{6}$	3	0	1	0	1	1	1	1	0	0
$M_{7}$	2	1	1	0	3	0	1	0	0	1
$M_{8}$	3	0	1	0	3	0	1	0	1	1
$M_{9}$	3	0	1	0	2	0	1	1	0	1

The rest unreachable states can be deduced by analogy. Finally, we find $R_{U} (N, M_{0}) = \cup_{j = 1}^{3} \cup_{i = 1}^{3} R_{ui}^{G_{j}} (N, M_{0})$ . In the sequel, to obtain the reachable states of $(N, M_{0})$ , we just need to exclude the elements of $R_{U} (N, M_{0})$ from $R_{B} (N, M_{0})$ . The reachable states of $(N, M_{0})$ are finally listed in Table 10.

Table 10.

Reachable states of $(N, M_{0})$ .

	$p_{1}$	$p_{2}$	$p_{3}$	$p_{4}$	$p_{5}$	$p_{6}$	$p_{7}$	$p_{8}$	$p_{9}$	$p_{10}$	$p_{11}$	$p_{12}$	$p_{13}$	$p_{14}$	$p_{15}$	$p_{16}$
$M_{1}$	4	0	0	0	0	4	0	0	0	0	0	0	1	1	1	1
$M_{2}$	3	1	0	0	0	4	0	0	0	0	0	0	0	1	1	1
$M_{3}$	3	0	1	0	0	4	0	0	0	0	0	0	1	0	1	1
$M_{4}$	2	1	1	0	0	4	0	0	0	0	0	0	0	0	1	1
⋮			⋮
$M_{99}$	3	0	0	1	0	3	0	1	0	0	0	0	1	0	0	1

Computational complexity analysis and comparison

In this section, we compare the computational complexity of computing the state space of an LS³PR by the proposed method with that by RG. First, if RG is applied to find reachable states, supposing that k and t denote the number of reachable states and the number of transitions, respectively, for any state M in reachability set, one needs to compute subsequent states, which requires t steps. Thus, its computational amount is $O (t)$ . Overall, considering all k reachable states in reachability set, the computational complexity of using RG to find reachable states is $O (t^{k})$ .

Second, if we use the proposed method to compute reachable states, it is found that its computational complexity contains three parts. Supposing that there are m operation places and n resource places, computing the reachable states of theory permissive needs at most $(m / n)^{n}$ steps. It costs $2^{n}$ computational amount when using the policy in the work by Wang et al.¹⁹ to find all SMSs and computing the unreachable states derived from each SMS requiring at most $(m / n - 2)^{n}$ steps. Hence, in this part, the computational complexity is $O (2^{n} • (m / n - 2)^{n})$ . And the third part, we need at most $(m / n)^{n}!$ steps to exclude all unreachable states from the set of reachable states of theory permissive. Consequently, putting them together, the computational complexity of using the proposed method is $O ((m / n)^{n} + 2^{n} • (m / n - 2)^{n} + (m / n)^{n}!)$ . Clearly, it greatly reduces the computational complexity although it is still an exponential complexity method.

Conclusion

This study presents a theory instead of RG to calculate the state space of an LS³PR. In deadlock prevention problems, we are committed to synthesizing optimal supervisors for plant nets. Hence, it is necessary to find all reachable states to synthesize an optimal or nearly optimal supervisor. The existing methods, such as RG, are difficult, even impossible, to find state space for a large net system due to its high computational complexity. This article pioneers the very first study to deal with a subclass of S³PR (LS³PR) by combinatorics. Excluding all unreachable states from the set of reachable states of theory permissive calculated by combinatorics, the left states are the reachable states of the considered LS³PR. Analysis shows its computational complexity is far lower than RG.

Footnotes

Academic Editor: Murat Uzam

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under Grant No. 61673309, the Fundamental Research Funds for the Central Universities under Grant Nos. JB160401 and JBG160415, the Scientific Research Program Funded by Shaanxi Provincial Education Department under Grant No. 16JK1342, the National Natural Science Foundation of China under Grant No. 51607133, the Natural Science Basic Research Plan in Shaanxi Province of China under Grant No. 2016JQ5106, the Science and Technology Project of Shaanxi Province under Grant No. 2016GY-136, the Doctoral Research Startup Funds of Xi’an Polytechnic University under Grant No. BS1335, and the Innovation and Entrepreneurship Training Program of Xi’an Polytechnic University under Grant No. 2016125.

References

Hou

Zhao

Liu

Deadlock control for a class of generalized Petri nets based on proper resource allocation. Asia J Control 2016; 18: 206–223.

ZW.

Deadlock analysis and control in resource allocation systems. Inform Sciences 2016; 363: 174–177.

Ghaffari

Rezg

Xie

XL.

Design of a live and maximally permissive Petri net controller using the theory of regions. IEEE T Robotic Autom 2003; 19: 137–142.

Zhou

Jeng

MD.

A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions. IEEE T Autom Sci Eng 2008; 5: 182–188.

Uzam

Zhou

MC.

An improved iterative synthesis approach for liveness enforcing supervisors of flexible manufacturing systems. Int J Prod Res 2006; 44: 1987–2030.

Uzam

Zhou

MC.

An iterative synthesis approach to Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE T Syst Man Cy A 2007; 37: 362–371.

Ezpeleta

Colom

Martinez

A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE T Robotic Autom 1995; 11: 173–184.

Esparza

Reachability in live and safe free choice Petri nets is NP-complete. Theor Comput Sci 1998; 198: 211–224.

Ferrarini

On the reachability and reversibility problems in a class of Petri nets. IEEE T Syst Man Cyb 1994; 24: 1474–1482.

10.

Kostin

AE.

Reachability analysis in T-invariant-less Petri nets. IEEE T Automat Contr 2003; 48: 1019–1024.

11.

Lipton

RJ.

The reachability problem requires exponential space. New Haven, CT: Yale University, 1976, p.62.

12.

Starke

PH.

INA: integrated net analyzer. Berlin: Handbuch, 1992.

13.

Chen

Khalgui

. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE T Autom Sci Eng 2011; 8: 374–393.

14.

Hong

Chao

DY.

Enumeration of reachable states for arbitrary marked graphs. IET Control Theory A 2012; 6: 1536–1543.

15.

Hong

Wang

Jing

. Combinatorics and resource circuit based enumeration of reachable states for S³PR. Adv Mech Eng 2016; 8: 1–11.

16.

Hong

Jing

Hou

. Combinatorics-based estimation of reachable states for the system of simple sequential process with resources. IEEJ Trans Electron Inf Syst 2016; 11: 134–141.

17.

Roberts

Tesman

Applied combinatorics. Oxford: Taylor & Francis, 2009.

18.

Zhou

MC.

Modeling, analysis, and deadlock control of automated manufacturing systems. Beijing, China: Science Press, 2009 (in Chinese).

19.

Wang

Jia

. An effective algorithm to find elementary siphons in a class of Petri nets. IEEE T Syst Man Cy A 2009; 39: 912–923.

On calculation of state space for linear system of simple sequential processes with resources

Abstract

Keywords

Introduction

Preliminaries

Petri nets

LS3PR

Definition 1

Definition 2

Definition 3

Property 1

Definition 4

Main approach

A simple example

IMs

Theorem 1

Corollary 1

Definition 5

Property 2

Property 3

Unreachable states exclusion

Definition 6

Theorem 2

Proof

Definition 7

Property 4

Lemma 1

Proof

Theorem 3

Proof

Definition 8

State estimate algorithm and example

Computational complexity analysis and comparison

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

LS³PR