Identification of one-place-unbounded Petri nets from their modified coverability graph

Abstract

This paper presents the problem of identifying a one-place unbounded Petri net. Given an unlabelled graph that represents the modified coverability graph of a net, we establish a Petri net model whose modified coverability graph is isomorphic to the unlabelled graph, and that can identify the weight of the arcs that cannot be obtained from the coverability graph of the net. Based on the partition of the nodes in the unlabelled graph, we guess and decide the structure of a Petri net and the weight of the arcs by an integer linear programming problem. The unknowns to be determined are the elements of the pre- and post-incidence matrices and the initial marking of the net, which can be computed by solving an integer linear programming problem. Finally, an example is used to validate the rationality and effectiveness of the proposed approach.

Keywords

Identification integer linear programming modified coverability graph Petri net unlabelled graph

Introduction

The identification of discrete event systems (DES) aims to obtain a mathematical model, which can depict the dynamic behaviour of DES by observing the evolution of input–outputs as well as other knowledge about the system behaviour (Estrada-Vargas et al., 2010). There are three main approaches for identifying DES, namely progressive identification (Meda-Campaña, 2002), parametric automata construction (Klein, 2005) and integer linear programming (ILP; Dotoli et al., 2008). However, the main disadvantage of the ILP approach cannot be applied to identify large and complex DES, because the computational complexity of the algorithm grows exponentially and solution of ILP is computationally expensive. In general, the objective of the identification problem mainly involves two issues: one is whether there exists a DES (e.g. a given Petri net) to generate the corresponding behaviour for a given behavioural characteristic; the other is whether an available procedure or algorithm can be provided to determine such a DES (e.g. an automaton or a Petri net).

During the past decade, the interest in the identification of DES has grown rapidly. Hiraishi (1992) discussed the problem of how to identify a safe Petri net, and presented an algorithm to construct a Petri net model from a finite set of firing sequences. Firstly, the language of a finite-state unlabelled graph was identified with the given firing sequences. Then the structure of a Petri net was conjectured based on the dependency relation extracted from the language. An original net could be uniquely identified when the language was generated by a special class of nets and at the same time a sufficiently large set of firing sequences were given. Based on the theory of regions, Badouel and Darondeau (1998) proposed an approach by constructing an unlabelled net, whose reachability graph was isomorphic, to a given unlabelled graph.

Recently, some efficient algorithms have also been designed to synthesize a net with the knowledge of linear algebra (Giua and Seatzu, 2005; Giua et al., 2005). Later on, a general approach was presented by Giua and Seatzu et al. to identify a Petri net system through solving an ILP problem (Cabasino et al., 2006a, 2007; Dotoli et al., 2008; Giua and Seatzu, 2005). First, they presented a given finite language, which was generated by an unknown free-labelled Petri net system, and was allowed to contain positive examples (strings that belonged to the language) and counterexamples (strings that did not belong to the language). Second, some structural constraints such as conservativeness and consistency were added to the net to make the resulting Petri net closer to the target system. Finally, the above research results were extended to the case of labelled Petri net systems.

Based on the construction of a set of integer linear constraints, Dotoli et al. (2008) presented an approach to identify a labelled Petri net model by performing real time observation of its behaviour evolution. This approach did not require complete knowledge of the system evolution in the form of the reachability graph, or the positive examples and counterexamples of the DES language. For a given unlabelled graph, Cabasino et al. (2007) proposed a method to synthesize a bounded Petri net system whose reachability graph was isomorphic, and the net system was obtained by solving an ILP problem from a similar algebraic characterization of the set of feasible constraints.

For a given graph, Cabasino et al. (2006b) presented a method about the identification of an unbound Petri net from its coverability graph (CG) with the purpose of finding a net system whose coverability graph is isomorphic. The unknown parameters contain elements of the pre- and post-incidence matrices and the initial marking of the net. However, the limitation of the above method is that: first, it cannot identify accurately the weight of the arcs in the net; second, it cannot generate an exact or an approximate net model for a big target Petri net system, because little information is revealed in the CG of a net; and third, the statement of an ILP problem from a set of state space is exponential. Two motivating examples are considered, as shown in Figures 1(a) and (b). Their CGs are shown in Figures 1(c) and 1(d), respectively. Figure 1(e) represents the same unlabelled graph. If the method presented in the above literature is adopted (Cabasino et al., 2006b), these two models cannot be identified by the CG of the net, because the loss of information caused by the ω symbol prevents us obtaining the weight of the arcs from the unlabelled graph. However, if we use the expression $ir + a$ to represent the value of the components of a marking, an optimization model can build on the modified coverability graph (MCG) or the modified unlabelled graph. That is, the weight of the arcs can be identified and obtained in the process of our approach. This is also the main motivation and contribution of our work. The computational complexity of our approach depends on the number of the nodes and transitions in the MCG.

Figure 1.

Parts (a) and (b) are one-place-unbounded Petri nets, (c) and (d) are the coverability graphs of (a) and (b), respectively, and (e) is the same unlabelled coverability graph for the nets in (a) and (b).

In this paper, we focus our attention on how to identify a one-place unbounded Petri net and how to deal with system identification in instances when a Petri net model cannot be determined by its CG (Cabasino et al., 2006b; Karp and Miller, 1969). Thus, we explore the problem of identifying a Petri net model from its MCG.

The purpose of identifying a Petri net is to determine the initial marking and the structure of a Petri net, i.e. the pre- and post-matrices, and make its MCG isomorphic to a given finite unlabelled graph G, which is given and represents the MCG of a net. These unknown elements can be obtained by solving an ILP problem. Consequently, a Petri net model can be determined such that its MCG is isomorphic to the unlabelled graph. At the same time, we may identify and obtain the weight of the arcs, which cannot be obtained from the CG of the net.

The rest of the paper is organized as follows. Some basic concepts and notations about Petri net theory and ω-number are introduced in the next section. The MCG and the relevant properties will be discussed, followed by the classification and partition of nodes. The method to synthesize a Petri net system from its unlabelled graph is demonstrated and finally conclusions are given.

Preliminaries

Petri net

The basic concepts and notations of a Petri net used in this paper are mostly taken from Giralt and Valk (2003). Let $Z$ , $N$ and $N^{+}$ denote the set of integers, non-negative integers and positive integers, respectively.

The structure of a Petri net is a four-tuple $Σ = (P, T, Pre, Post)$ , where $P$ is a set of $m$ places represented by circles, $T$ is a set of $n$ transitions represented by bars, the pre-incidence function $Pre : P \times T \to N$ expresses the relation from the places to the transitions, and the post-incidence function $Post : P \times T \to N$ expresses the relation from the transitions to the places. The $m \times n$ matrix $C = Post - Pre$ is called the incidence matrix of a Petri net. The pre-set and post-set of a node $X$ ( $X \in P \cup T$ ) are denoted by $• X$ and $X^{•}$ , respectively. A node $X$ ( $X \in P \cup T$ ) is called the source node if it has no input arcs, i.e. $• X = ϕ$ ( $ϕ$ is a null set). A node $X$ ( $X \in P \cup T$ ) is called a sink node if it has no output arcs, i.e. $X^{•} = ϕ$ .

A mapping $M : P \to N$ is a state (or marking) vector. The number $M (p)$ is called the marking of the place $p$ . The vector $M_{0}$ is the initial marking of the net. Thus, a Petri net system is denoted by $(Σ, M_{0})$ . A transition $t \in T$ is enabled at a marking $M$ if and only if $M \geq Pre (\cdot, t)$ and may fire to yield a marking $M'$ , denoted $M [t > M'$ . A marking $M'$ is reachable from $M$ by the firing of a transition sequence $σ$ , denoted $M [σ > M'$ . $M'$ can be computed by using the state equation: $M^{'} = M + C \cdot \overset{⇀}{σ}$ , where $\overset{⇀}{σ} \in N^{n}$ is denoted the firing vector(or $T$ -vector) of the sequence $σ$ .

The set of all markings reachable from $M_{0}$ is defined as the reachability set of $(Σ, M_{0})$ and is denoted $R (Σ, M_{0})$ . Define the free-language of a Petri net system $(Σ, M_{0})$ as the set of its firing sequences:

L (Σ, M_{0}) = {σ \in T^{*} | M_{0} [σ >}

Definition 1 (Cabasino et al., 2007). Given a Petri net $(Σ, M_{0})$ , a $T$ -vector $\overset{⇀}{σ} : T \to N$ , with $\overset{⇀}{σ} \neq \overset{⇀}{0}$ , is called:

T-invariant: if $C \cdot \overset{⇀}{σ} = \overset{⇀}{0}$ , i.e. the corresponding firing transition sequence does not change the number of tokens of the places;

T-increasing: if $C \cdot \overset{⇀}{σ} \underset{\neq}{>} \overset{⇀}{0}$ , i.e. the corresponding firing transition sequence increases the number of tokens of the places;

T-decreasing: if $C \cdot \overset{⇀}{σ} \underset{\neq}{<} \overset{⇀}{0}$ , i.e. the corresponding firing transition sequence decreases the number of tokens of the places.

ω-number and ω-vector

The ω-number and ω-vector to investigate in this research is the expression $ir + a$ , which was first proposed by Peterson (1981). Some definitions related to this paper are given below.

Definition 2 (Wang et al., 2004). A set $S$ is called an ω-number, if there exists $r \in N^{+}$ , $n, a \in Z$ , such that $S = {ir + a | i \geq n}$ , which can also be expressed uniquely as:

S = ω (r, n, a) \equiv r ω_{n} + a \equiv {ir + a | r \in N^{+}, n \in Z, 0 \leq a < r, i \geq n}

where $r$ , $n$ , $i$ and $a$ are the base, the lower bound, the coefficient variable and the reminder of an ω-number, respectively. For the structure of the infiniteness, ω-numbers can exhibit more information than ω does.

Definition 3. A vector x is called an ω-vector if at least one of a vector’s coordinates is an ω-number. Any ordinary vector of an ω-vector is called an instance. For instance, an instance of the ω-vector ${(1, 0, 2 ω_{1} + 1)}^{T}$ is ${(1, 0, 3)}^{T}$ , which is also the least instance.

Definition 4.

Given two ω-numbers $ω (r, n, a)$ and $\tilde{ω} (r, m, a)$ , $ω (r, n, a) \leq \tilde{ω} (r, m, a)$ if $n \leq m$ .

Given two ω-vectors $x = {(x_{1}, x_{2}, \dots, x_{n})}^{T}$ and $y = {(y_{1}, y_{2}, \dots, y_{n})}^{T}$ , $x$ contains $y$ if $x_{i} \leq y_{i}$ , $i = 1, 2, \dots, n$ and they have the same non-ω-number coordinates.

For an integer $b \in Z$ , it is defined that $ω (r, n, a) + b = ω (r, n + s, c)$ where $a + b = sr + c$ , $s \in Z$ , $0 \leq c < r$ .

Note that subtraction is defined as that b is allowed to be negative in this definition.

Definition 5 (Ding et al., 2008). A transition t is called conditionally enabled at the ω-markings, i.e. represented by an ω-vector, if a transition t is not enabled at a specific marking M whose ω-number components are set to be the lower bound of the coefficient variables. For instance, transition $t_{2}$ is conditionally enabled at ${(1, 0, 2 ω_{0})}^{T}$ in Figure 2(c), but $t_{1}$ is not conditionally enabled at ${(1, 0, 2 ω_{0})}^{T}$ .

Figure 2.

The schematic diagram of a Petri net. (a) An unbounded Petri net; (b) the modified reachability tree (MRT); (c) the modified coverability graph (MCG); (d) the unlabelled MCG.

Figure 3.

A sketch from Figure 2(d).

Figure 4.

A sketch from Figure 2(d).

The MCG and its algorithm

Our identification approach is based on the construction of the modified reachability tree/graph of unbounded Petri nets (Ding et al., 2008; Wang et al., 2010).

Algorithm 1. Construction of the MRT for an unbounded Petri net

1) The initial marking $M_{0}$ is denoted a frontier node $x$ , i.e. a root node.

2) The frontier node $x$ will be processed if a frontier node exists. Otherwise, terminate.

2.1) If there exists another non-frontier node $y$ such that $M [x] = M [y]$ , i.e. it has the same marking with the node $x$ , then $x$ is an $ω$ -duplicate node; goto 2.

2.2) If there exists another node $y$ covering node $x$ , i.e. $M [x] \leq M [y]$ , then $x$ is an $ω$ -duplicate node; goto 2.

2.3) If each transition $t \in T$ is not enabled at the marking $M [x]$ , then $x$ is a terminal node; goto 2.

2.4) If there exists a transition $t \in T$ which is enabled at $M [x]$ , then it may fire at $M [x]$ and yields $δ (M [x], t)$ . A new node $z$ is generated in the MRT, and the marking $M [z]$ is created as following:

2.4.1) If there exists a node $y$ on the path from the root node to node $x$ such that for some places $s \in P$ : $M [y] (s) \leq δ (M [x], t) (s)$ , and for other places $s' \in P$ , $M [y] (s') = δ (M [x], t) (s')$ , then $M [z] (s) = ω (r, n, a)$ , where $r = δ (M [x], t) (s) - M [y] (s)$ , $n = δ (M [x], t) (s) \ r$ (the symbol $' \'$ means to divide to get the integer quotient) and $a = δ (M [x], t) (s) % r$ (the symbol % means to divide to get the integer remainder.)

2.4.2) The base $r$ is recorded and stored.

2.4.3) Otherwise, for each $s$ : $M [z] (s) = δ (M [x], t) (s)$ .

2.4.4) If $t$ is conditionally enabled at $M [x]$ , then a dash arc is directed from $x$ to node $z$ in the MRT. Otherwise a solid arc is directed from $x$ to $z$ . Now, $z$ becomes a new frontier node.

2.5) Redefine node $x$ as an interior node; goto 2.

From the MRT, the MCG can be obtained by fusing the same or duplicate nodes in the tree. However, the label and the arc among the nodes do not change. Conversely, an MCG can be always converted into an MRT in an unlabelled graph. In step 2.4.1, the firing of a transition t leads to $M [y] (s) \leq δ (M [x], t) (s)$ for the marking of some place s. Repeat the process, then the marking of the place $s$ grows unbounded, denoted $ω (r, n, a)$ , i.e. $r ω_{n} + a$ , where $r = δ (M [x], t) (s) - M [y] (s)$ , which is recorded and stored. The tokens of the remaining places do not change.

Definition 6. In step 2.4.1 of the above algorithm, by the firing of a transition $t$ a node $x$ , which has no $ω$ component, is changed to the node $z$ , which has one component $ω$ . Otherwise, the coefficient variable or the lowest bound of the $ω$ -number components of the node $z$ is increased.

The node $z$ is called an $ω$ -increasing node and the corresponding marking is called an $ω$ -increasing marking.

The production associated with the path on the graph

π : y \overset{σ}{➝} x \overset{t}{➝} z

is called an $ω$ -increasing production.

Any production of the form in the above graph defined as $s (π) = y$ is the start node of the production, $e (π) = z$ is the end node and $l (π) = σ t$ is the corresponding transition sequence. The set of the nodes in a production $π$ is denoted $v (π)$ .

$Δ_{↑}$ is denoted the set of $ω$ -increasing production, $Δ_{↑}^{k}$ is the set of $ω$ -increasing production that ends in $x_{k}$ , which is called an $ω$ -increasing marking.

Remark 1. In this case, an $ω$ -increasing production is different from $ω$ -increasing production in Cabasino (2006b), which only means that the number of $ω$ components of a node is increased. For instance, a node ${(ω, 1)}^{T}$ is changed to ${(ω, ω)}^{T}$ as shown in Figure 1(c), which is an $ω$ -increasing production. However, a node ${(1, 0, 0)}^{T}$ is changed to ${(1, 0, 2 ω_{1})}^{T}$ , and a node ${(1, 0, 2 ω_{0})}^{T}$ is changed to ${(1, 0, 2 ω_{0} + 1)}^{T}$ , as shown in Figure 2(b), which are $ω$ -increasing productions in this paper.

Similarly, we give definitions about the $ω$ -decreasing and $ω$ -stationary node from the Algorithm 1.

Definition 7. The production associated with the path on the graph

π : y \overset{σ}{➝} x \overset{t}{⤏} z

is called an $ω$ -decreasing production, i.e. transition $t$ is conditionally enabled at the node $x$ . The node $z$ is called an $ω$ -decreasing node and the corresponding marking is called an $ω$ -decreasing marking.

$Δ_{↓}$ is denoted the set of $ω$ -decreasing production, $Δ_{↓}^{k}$ is the set of $ω$ -decreasing production that ends in $x_{k}$ , which is called an $ω$ -decreasing marking.

Remark 2. In this case, $ω$ -decreasing production only means that the coefficient variable or the lowest bound of the $ω$ -number components of a node is decreased. For instance, a node ${(0, 1, 2 ω_{0})}^{T}$ is changed to ${(1, 0, 2 ω_{0} + 1)}^{T}$ , as shown in Figure 2(b), which is an $ω$ -decreasing production.

Definition 8. The production associated with the path on the graph

π : y \overset{σ}{➝} x \overset{t}{➝} y

is called an $ω$ -stationary production. The node $y$ is called an $ω$ -stationary node and the corresponding marking is called an $ω$ -stationary marking.

$Δ_{\to}$ is denoted the set of $ω$ -stationary productions, $Δ_{\to}^{k}$ is the set of $ω$ -stationary productions that ends in $x_{k}$ , which is called an $ω$ -stationary marking.

Remark 3. In this case, $ω$ -stationary production only means that the coefficient variable or the lowest bound of the $ω$ -number components of a node is not changed. For instance, a node ${(1, 0, 2 ω_{1})}^{T}$ is changed to ${(0, 1, 2 ω_{1})}^{T}$ as shown in Figure 2(b), which is an $ω$ -stationary production.

Example 1. A net is given in Figure 2(a), whose MRT and MCG are shown in Figures 2(b) and (c), respectively. The unlabelled MCG is given in Figure 2(d).

Sequence $t_{1}$ is a repetitive sequence, which yields ${(1, 0, 2)}^{T}$ from $M_{0} = {(1, 0, 0)}^{T}$ and increases the marking of place $p_{3}$ . Hence in the MCG we easily identify that $x_{1}$ is an $ω$ -increasing node and the corresponding $ω$ -increasing production is $π : x_{0} t_{1} x_{1}$ , which leads to node $e (π) = x_{1}$ from $s (π) = x_{0}$ with label $M_{1} = {(1, 0, 2 ω_{1})}^{T}$ .

Sequence $t_{3}$ yields ${(0, 1, 2 ω_{0})}^{T}$ from ${(0, 1, 2 ω_{1})}^{T}$ and decreases the marking (i.e. the tokens) of place $p_{3}$ . Meanwhile, $t_{3}$ is conditionally enabled at $x_{6}$ . Hence in the MCG we have an $ω$ -decreasing production $π : x_{2} t_{3} x_{6}$ , which leads to node $e (π) = x_{6}$ from $s (π) = x_{2}$ with label $M_{6} = {(1, 0, 2 ω_{0})}^{T}$ .

Sequence $t_{2} t_{4} t_{2} t_{4} t_{1}$ yields ${(0, 1, 2 ω_{1})}^{T}$ from ${(0, 1, 2 ω_{1})}^{T}$ and does not change the marking of place $p_{3}$ . Hence in the MCG we have an $ω$ -stationary production $π : x_{1} t_{2} x_{2} t_{4} x_{3} t_{2} x_{4} t_{4} x_{5} t_{1} x_{1}$ , which leads to node $e (π) = x_{1}$ from $s (π) = x_{1}$ with label $M_{1} = {(1, 0, 2 ω_{1})}^{T}$ . From the unlabelled MCG in Figure 2(d), we obtain a proposition that can recognize the markings or paths associated with $ω$ -increasing, $ω$ -decreasing and $ω$ -stationary markings, and the corresponding productions.

Proposition 1. Given the MCG of a Petri net, we consider a node $z$ and a production $π$ , then the following conclusions hold:

A node $z$ is $ω$ -increasing and $π$ is the corresponding $ω$ -increasing production if in the unlabelled graph there exists a node $x \neq z$ , which satisfies $s (π) = x$ , $e (π) = z$ , and there exists another production $π'$ such that $s (π') = e (π') = z$ , $l (π) = σ \subseteq l (π') = σ'$ (i.e. the transitions in the sequence $σ$ are contained in the sequence $σ'$ ), $v (π) \cap v (π') = {z}$ and a solid arc is directed from z to z.

A node $z$ is $ω$ -decreasing and $π$ is the corresponding $ω$ -decreasing production, if in the unlabelled graph there exists a node $x \neq z$ , which satisfies $s (π) = x$ , $e (π) = z$ , and there exists another production $π'$ such that $s (π') = e (π') = z$ , $l (π) = σ \subseteq l (π') = σ'$ , and a dash arc is directed from z to z.

A node $z$ is $ω$ -stationary and $π$ is the corresponding $ω$ -stationary production if in the unlabelled graph there exists a node $z$ , which satisfies $s (π) = z$ , $e (π) = z$ , and a solid arc is directed from $z$ to $z$ , for $z \in v (π)$ .

Proof:

As explained in the construction of the MCT, a node $z$ is $ω$ -increasing and $π$ is the corresponding $ω$ -increasing production, if and only if there exists a node $y$ and a sequence $σ$ such that $M [y] \leq δ (M [x], t)$ and $δ {(M [x], t)}_{i} = nr + a$ for all those places $p$ where $M {[y]}_{i} < δ {(M [x], t)}_{i}$ and $M {[y]}_{j} = δ {(M [x], t)}_{j}$ for $j \neq i$ . Since $σ$ is enabled at $M [y]$ , it is enabled at the greater marking $δ (M [x], t)$ . However, since a sequence $σ'$ contains $σ$ fire and does not change the marking of a place $p$ such that $δ {(M [x], t)}_{i} < nr + a$ , its firing from $δ (M [x], t)$ leads back to $δ (M [x], t)$ . Finally, $π$ is $ω$ -increasing if and only if $e (π)$ contains at least one $ω$ -component with respect to all nodes in $v (π) \ e (π)$ . This implies that $v (π) \cap v (π') = e (π)$ .

A node $z$ is $ω$ -decreasing and $π$ is the corresponding $ω$ -decreasing production, if and only if there exists a node $y$ and a sequence $σ$ such that $M [y] \geq δ (M [x], t)$ and $δ {(M [x], t)}_{i} = nr + a$ for all those places $p$ where $M {[y]}_{i} > δ {(M [x], t)}_{i}$ and $M {[y]}_{j} = δ {(M [x], t)}_{j}$ for $j \neq i$ . Since $σ$ is enabled at $M [y]$ , it is conditionally enabled at the less marking $δ (M [x], t)$ . However, since a sequence $σ'$ contains $σ$ fire and does not change the marking of a place $p$ such that $δ {(M [x], t)}_{i} < nr + a$ , its firing from $δ (M [x], t)$ leads back to $δ (M [x], t)$ . Finally, $π$ is $ω$ -decreasing if and only if $e (π)$ contains at least one $ω$ -component with respect to all nodes in $v (π) \ e (π)$ .

A sequence $σ$ is $ω$ -stationary with respect to an unbounded place if and only if it does not modify the token content of places that are not associated with $ω$ -components if and only if $s (π) = e (π) = z$ .▪

Example 2.

In Figure 2(d), we observe two productions: $π : x_{0} \overset{t_{1}}{➝} x_{1}$ and $π' : x_{1} \overset{t_{2} t_{4} t_{2} t_{4} t_{1}}{➝} x_{1}$ , and the transition sequence $l (π) = t_{2} t_{4} t_{2} t_{4} t_{1}$ contains $l (π') = t_{1}$ . Thus $x_{1}$ is an $ω$ -increasing node and the corresponding $ω$ -increasing production is $π : x_{0} t_{1} x_{1}$ .

Let us observe the following two productions as shown in Figure 2(d), and the transition sequence $l (π) = t_{3}$ equals to $l (π') = t_{3}$ ,

π : x_{2} \overset{t_{3}}{\to} x_{6}, x_{6} \overset{t_{3}}{⤏} x_{6} .

Thus $x_{6}$ is an $ω$ -decreasing node and the corresponding $ω$ -decreasing production is $π : x_{2} t_{3} x_{6}$ .

Definition 9. Given a node $x_{k} \in Ω$ , a production $π_{k} : x_{0} \overset{σ_{k}}{➝} x_{k}$ is called the minimal production, if the production does not contain repetitive sequences, where $σ_{k} = σ (π_{k})$ is the associated sequence.

Definition 10. Two minimal productions $π_{k}$ and $π'_{k}$ are called the equivalence production, if they end in the same node $x_{k}$ and $σ_{k} = l (π_{k}) \neq l (π'_{k}) = σ'_{k}$ , denoted $Θ = {(σ_{k}, σ'_{k}, x_{k}) | σ_{k} = l (π_{k}) \neq l (π'_{k}) = σ'_{k}, s (π) = s (π'), e (π_{k}) = e (π'_{k}) = x_{k}}$ .

Example 3. In Figure 2(d), we observe two productions: $π : x_{2} t_{3} x_{6}$ , $π' : x_{2} t_{4} x_{3} t_{2} x_{4} t_{4} x_{5} t_{2} x_{6}$ . Apparently, they satisfy $s (π) = s (π') = x_{2}$ , $e (π) = e (π') = x_{6}$ and $σ = t_{3} \neq t_{4} t_{2} t_{4} t_{2} = σ'$ ; then these two productions are the equivalence production by the above definition.

For the sake of simplicity, we merely consider a one-place unbounded Petri net and the following assumptions will be satisfied:

A1) We only identify Petri nets that satisfy the necessary and sufficient conditions given in Proposition 1.

A2) The number of places is known.

A3) Only one place is unbounded.

Classification and partition of nodes

In this section, we will discuss the classification and partition of nodes, which is extremely useful for our identification problem.

Theorem 1 (Wang et al., 2004). The modified reachability tree of a Petri net is finite.

From the above theorem, we know that the nodes of an MRG or MCG are finite, denoted $Ω$ , i.e. $Ω = {x_{0}, x_{1}, \dots, x_{n}}$ $= Ω_{I} \cup Ω_{ω}$ , where $Ω_{I}$ is the set of the nodes that have no $ω$ component and $Ω_{ω}$ is the set of the nodes that have $ω$ components. Thus we can determine an initial partition of the nodes in the form of $ω$ components. An algorithm is proposed to partition the set of the nodes of an MCG according to the least instance of $ω (r, n, a)$ . Simultaneously, we refine the partition by two given rules.

Rule 1: Two subsets $Ω_{i}$ and $Ω_{j}$ $(i \neq j)$ can be merged if the following predications hold:

There exist two nodes $x \in Ω_{i}$ and $x' \in Ω_{j}$ such that $δ (x, t) = x'$ for some transitions $t \in T$ .

There does not exist an $ω$ -increasing production or $ω$ -decreasing production $π$ such that $s (π) = x$ and $e (π) = x'$ . That is, the $ω$ -components of their corresponding $ω$ -markings are the same, i.e. $M {[x]}_{ω} = ω (r, n, a)$ and $M {[x']}_{ω} = ω (r', n', a')$ ( $M {[•]}_{ω}$ represents the $ω$ -component of a node), where $r = r'$ , $n = n'$ , $a = a'$ .

Rule 2: For any two nodes $x \in Ω_{i}$ and $y \in Ω_{j}$ ( $Ω_{i} \cap Ω_{j} = ϕ$ ), if the following predications hold:

The node $y$ is an $ω$ -duplicate node with an $ω$ -marking and is also contained by another node that appears previously in the tree along the same path.

There does not exist a node $z$ such that $M [z] = M [y]$ , where $y$ has the same potential enabled transitions with $x$ , then the nodes $x$ and $y$ will be merged, the label and the arc between the nodes do not change.

For example, the node $x_{7}$ is an $ω$ -duplicate and there exist the same potential enabled transitions $t_{1}, t_{2}$ with node $x_{1}$ , so $x_{7}$ is merged with $x_{1}$ . Similarly, node $x_{8}$ is merged with $x_{3}$ , as shown in Figure 2(d).

Algorithm 2. Partition of an unlabelled MCG

Give an initial partition of the graph in terms of strongly connected components,

Ω_{I} \cup Ω_{0} \cup \dots \cup Ω_{h}

If there exist $Ω_{i}$ and $Ω_{j}$ , which satisfy the Rule 1, then we merge $Ω_{i}$ and $Ω_{j}$ .

If there exist $x$ and $y$ , which satisfy the Rule 2, then we merge $x$ and $y$ .

The final partition: $Ω_{I} \cup Ω_{ω 0} \cup \dots \cup Ω_{ω k}$ , $k \leq h$ , is obtained, where $ω i$ represents the least instance of the $ω (r, n, a)$ component of the nodes in $Ω_{ω i}$ , $i = 0, 1, \dots, k$ .

The subsets $Ω_{ω 0}, \dots, Ω_{ω k}$ are ordered in the light of the least instance of $ω$ -number. Given two $ω$ -numbers $ω (r, n, a)$ and $ω (r', n', a')$ , $ω (r, n, a) ≺ ω (r', n', a')$ is defined because $rn + a \leq r' n' + a'$ . Thus a partial order of the partition of the nodes is obtained:

Ω_{I} ≺ Ω_{ω 0} ≺ \dots ≺ Ω_{ω k}

Thus, according to Algorithm 2, the unlabelled MCG in Figure 2(d) can be changed into the following form.

Remark 4. In the beginning, the procedure of our identification is dependent on the partition of the nodes in the unlabelled graph or the MCG. If there exists a transition $t \in T$ such that $δ (x_{i}, t) = x_{j}$ , for $x_{i} \in Ω_{ω i}$ and $x_{j} \in Ω_{ω j}$ , then the constant $r = | ω j - ω i |$ in the constraint (c1) or (d1).

Example 4. We observe the unlabelled MCG in Figure 5. The initial partition is $Ω_{I} = {x_{0}}$ and $Ω_{ω} = Ω_{1} \cup Ω_{2} \cup \dots \cup Ω_{6} = {x_{1}} \cup {x_{2}} \cup \dots \cup {x_{6}}$ . By the above algorithm, we merge $Ω_{1}$ with $Ω_{2}$ , $Ω_{3}$ with $Ω_{4}$ and $Ω_{5}$ with $Ω_{6}$ , respectively. The node $x_{1}$ is merged with $x_{7}$ , and the node $x_{3}$ is merged with $x_{8}$ . Then the final partition is $Ω_{I} = {x_{0}}$ , $Ω_{ω 0} = {x_{5}, x_{6}}$ , $Ω_{ω 1} = {x_{3}, x_{4}}$ and $Ω_{ω 2} = {x_{1}, x_{2}}$ . Thus $Ω_{I} ≺ Ω_{ω 0} ≺ Ω_{ω 1} ≺ Ω_{ω 2}$ .

Figure 5.

The simplified modified coverability graph (MCG) in Figure 2(d).

Corollary 1. Given the MCG of a Petri net, the partial order of the partition of the nodes is obtained: $Ω_{I} ≺ Ω_{ω 0} ≺ \dots ≺ Ω_{ω k}$ . If there exists a transition $t \in T$ such that $δ (x_{i}, t) = x_{j}$ , for $x_{i} \in Ω_{ω i}$ , $x_{j} \in Ω_{ω j}$ , then the following conclusions hold:

If $Ω_{ω i} ≺ Ω_{ω j}$ , the transition $t$ is T-increasing for the unbounded place and the corresponding production is $ω$ -increasing production. Moreover, the constant $r$ of the constraint (c1) equals to $ω j - ω i$ .

If $Ω_{ω j} ≺ Ω_{ω i}$ , the transition $t$ is T-decreasing for the unbounded place and the corresponding production is $ω$ -decreasing production. Moreover, the constant $r$ of the constraint (d1) equals to $ω i - ω j$ .

If $Ω_{ω i} = Ω_{ω j}$ , the transition $t$ is T-invariant for the unbounded place and the corresponding production is $ω$ -stationary production.

Proof. The proof is straightforward from the definitions of $ω$ -increasing production, $ω$ -decreasing production and $ω$ -stationary production. ▪

Note that the above conclusions are incorrect, if transition $t$ is conditionally enabled.

Synthesis of a Petri net system from its unlabelled MCG

In this section we consider a problem of determining a net $(Σ, M_{0})$ with the set of transition $T$ . Given a graph $G$ whose edges are labelled with the elements of $T$ , the MCG of the net $(Σ, M_{0})$ is isomorphic to $G$ under the assumptions A1–A3.

Problem 1. Given a finite state graph $G = (Q, T, δ, x_{0})$ with a set of places $P$ of cardinality $m$ , we want to identify the structure of one-place unbounded Petri net $Σ = (P, T, Pre, Post)$ and an initial marking $M_{0}$ such that the MCG of the net system $(Σ, M_{0})$ is isomorphic to $G$ . In fact, the unknown parameters are the elements of the two matrices $Pre$ , $Post \in N^{m \times n}$ and the initial marking $M_{0} \in N^{m}$ .

To find a solution to Problem 1, a set of linear algebraic constraints are given first. We prove that a net system $(Σ, M_{0})$ , which satisfies the given set of constraints, is a solution to Problem 1 and vice versa. However, we only give the sketch of the proof and explain the meaning of each type of constraints. Let us first define two sets as follows:

$E = {(x, t) \in Q \times T | δ (x, t) i s^{} defined}$ , i.e. transition $t$ is enabled or conditionally enabled at the state $x$ .

$D = {(x, t) \in Q \times T | δ (x, t) i s^{} no t^{} defined}$ , i.e. transition $t$ is not enabled at the state $x$ .

The following theorem characterizes the set of solutions to Problem 1.

Theorem 2. A net system $(Σ, M_{0})$ is a solution to the identification Problem 1 if and only if it satisfies the following set of linear constraints:

ϕ (E, D) = {\begin{array}{l} P o s t, P r e, \in Ν^{m \times n} \\ M_{0} \in N^{m} \\ M_{0} + P o s t \cdot {\vec{σ}}_{k} - P r e \cdot ({\vec{σ}}_{k} + {\vec{t}}_{j}) \geq 0, & \forall (x_{k}, t_{j}) \in E, & (a) \\ M_{0} + P o s t \cdot {\vec{σ}}_{k} - P r e \cdot ({\vec{σ}}_{k} + {\vec{t}}_{j}) - K \cdot {\vec{s}}_{k, j} \leq - {\vec{1}}_{m}, & \forall (x_{k}, t_{j}) \in D, & (b 1) \\ {\vec{1}}^{T} \cdot {\vec{s}}_{k, j} \leq m - 1, & \forall (x_{k}, t_{j}) \in D, & (b 2) \\ P o s t \cdot \vec{σ} - P r e \cdot \vec{σ} - r \cdot {\vec{s}}_{k} \geq 0, & \forall π \in Δ_{↑}, & (c 1) \\ - (P o s t \cdot \vec{σ} - P r e \cdot \vec{σ}) + K \cdot {\vec{s}}_{k} \geq 0, & \forall π \in Δ_{↑}, & (c 2) \\ - (P o s t \cdot \vec{σ} - P r e \cdot \vec{σ}) - r \cdot {\vec{s}}_{k} + K \cdot {\vec{s}}_{k}^{c} \geq 0, & \forall π \in Δ_{↓}, & (d 1) \\ P o s t \cdot \vec{σ} - P r e \cdot \vec{σ} + K \cdot {\vec{s}}_{k} \geq 0, & \forall π \in Δ_{↓}, & (d 2) \\ P o s t \cdot \vec{σ} - P r e \cdot \vec{σ} + K \cdot {\vec{s}}_{k} \geq \overset{⇀}{0} & \forall π \in Δ_{\to}, & (e 1) \\ - (P o s t \cdot \vec{σ} - P r e \cdot \vec{σ}) + K \cdot {\vec{s}}_{k} \geq \overset{⇀}{0} & \forall π \in Δ_{\to}, & (e 2) \\ P o s t \cdot ({\overset{⇀}{σ}}_{k} - {\vec{σ}}^{'}_{k}) - P r e \cdot ({\overset{⇀}{σ}}_{k} - {\vec{σ}}^{'}_{k}) + K \cdot {\vec{s}}_{k} \geq \overset{⇀}{0} & \forall (σ_{k}, {σ^{'}}_{k}, x_{k}) \in Θ, & (f 1) \\ - P o s t \cdot ({\overset{⇀}{σ}}_{k} - {\vec{σ}}^{'}_{k}) + P r e \cdot ({\overset{⇀}{σ}}_{k} - {\vec{σ}}^{'}_{k}) + K \cdot {\vec{s}}_{k} \geq \overset{⇀}{0} & \forall (σ_{k}, {σ^{'}}_{k}, x_{k}) \in Θ, & (f 2) \\ {\overset{⇀}{s}}_{k}, {\overset{⇀}{s}}_{k, j} \in {0, 1}^{m} \end{array}

(1)

where $s_{k} (p) = 1$ if $p = ω (r, n, a)$ ; otherwise, $s_{k} (p) = 0$ . $\vec{σ}$ and ${\vec{σ}}_{k}$ are the firing vectors associated with the generic productions $π$ and $π_{k}$ , respectively. ${\overset{⇀}{s}}_{k}^{c}$ is called the complement of ${\overset{⇀}{s}}_{k}$ , if the following equation holds: ${\vec{s}}_{k} + {\vec{s}}_{k}^{c} = {\vec{1}}_{m}$ . $K$ is a very large constant ( $K$ must be larger than the maximum expected weight of pre- and post-arcs).

Proof.

(a) Constraint (a) is the enabling constraint, i.e. transition $t_{j}$ is enabled at $M_{0} + Post \cdot {\vec{σ}}_{k} - Pre \cdot {\vec{σ}}_{k} = M_{k}$ if and only if $M_{k} (p) \geq Pr e (p, t_{j})$ , $\forall p \in P$ . That is, $M_{0} + Post \cdot {\vec{σ}}_{k} - Pre \cdot ({\vec{σ}}_{k} + {\vec{t}}_{j}) \geq 0$ .

(b) Constraints (b1) and (b2) are disabling constraints: if transition $t_{j}$ is not enabled at $M_{0} + Post \cdot {\vec{σ}}_{k} - Pre \cdot {\vec{σ}}_{k} = M_{k}$ , then at least for one place $p$ , the following inequality must hold: $M_{k} (p) < Pr e (p, t_{j})$ , i.e.

M_{0} (p) + Post (p, \cdot) \cdot {\vec{σ}}_{k} - Pre (p, \cdot) \cdot {\vec{σ}}_{k} \leq Pr e (p, \cdot) \cdot {\vec{t}}_{j} - 1

(2)

s_{k, j} (p) = 0 \Leftrightarrow M_{k} (p) \leq Pr e (p, t_{j}) - 1, \forall p \in P

(2)

(d) Assume that each component of $M_{k}$ is less than or equal to $K$ , i.e. $max_{p \in P} {M_{k} (p)} \leq K$ , then the component of ${\vec{s}}_{k, j}$ relative to the place $p$ must satisfy the inequality

M_{k} (p) - K \cdot s_{k, j} (p) \leq Pr e (p, t_{j}) - 1

(3)

(e) so that $M_{k} (p) < Pr e (p, t_{j})$ must hold if $s_{k, j} (p) = 0$ , while the Equation (3) is trivially verified if $s_{k, j} (p) = 1$ . Because all the variables are integers, Equation (3) can be rewritten in the vector form as:

M_{0} + Post \cdot {\vec{σ}}_{k} - Pre \cdot ({\vec{σ}}_{k} + {\vec{t}}_{j}) - K \cdot {\vec{s}}_{k, j} \leq - {\vec{1}}_{m}

(4)

(f) If ${\vec{1}}^{T} \cdot {\vec{s}}_{k, j} \leq m - 1$ , one $s_{k, j} (p)$ is null at least. Thus at least there exists one place that disables $t_{j}$ .

(c) If $s_{k} (p) = 0$ , the firing of the transition sequence associated with $π$ will not increase the token contents of $p$ , as imposed by the above constraints. If $s_{k} (p) = 1$ , $P o s t \cdot \vec{σ} - P r e \cdot \vec{σ} \geq r$ must hold (here $r = | ω j - ω i |$ expresses the number of token increased in the place $p$ ), which is equivalent to imposing the first constraint, while the constraint (c2) is trivially verified.

(d) If $s_{k} (p) = 1$ , then $s_{k}^{c} (p) = 0$ , i.e. $Post (p, \cdot) \cdot \vec{σ} - Pre (p, \cdot) \cdot \vec{σ} \leq - r$ (here $r = | ω j - ω i |$ ), which means that the firing of the transition sequence associated with $π$ decreases the token contents of $p$ as imposed by the above constraints. If $s_{k} (p) = 0$ , then $s_{k}^{c} (p) = 1$ , so $P o s t \cdot \vec{σ} - P r e \cdot \vec{σ} \leq K$ must hold. The constraint (d2) is trivially verified.

(e) By the Definition 8, the production $π$ should not change the marking of all the places $p = ω (r, n, a)$ for any $x \in Ω$ . In fact, if $s_{k} (p) = 0$ , then ${Post (p, \cdot) - Pre (p, \cdot)} \cdot \vec{σ} = 0$ , while if $s_{k} (p) = 1$ , the constraints are trivially verified.

(f) If $s_{k} (p) = 0$ , by Definition 9 the following equation holds ${Post (p, \cdot) - Pre (p, \cdot)} \cdot {\vec{σ}}_{k} = {Post (p, \cdot) - Pre (p, \cdot)} \cdot \vec{σ}$ for $p \in P$ . If $s_{k} (p) = 1$ , the constraints can be trivially obtained.▪

In general, there exist more than one Petri net system $(Σ, M_{0})$ (i.e. the solution to the sets (1) is not unique) such that the MCG of the net system $(Σ, M_{0})$ is isomorphic to $G$ . Thus a performance index $f (Post, Pre, M_{0})$ can be introduced to determine a Petri net system by minimizing the considered performance index. In particular, the objective function can be chosen to minimize the number of initial markings and the number of arcs in the net, i.e.

f (Post, Pre, M_{0}) = {\vec{1}}^{T} \cdot Post \cdot \vec{1} + {\vec{1}}^{T} \cdot Pre \cdot \vec{1} + {\vec{1}}^{T} \cdot M_{0}

(5)

Consequently, an identification problem can be formally presented as follows.

Problem 2. Given a performance index $f (Post, Pre, M_{0})$ and the identification problem 1 is considered, the solution to the problem 1 that minimizes $f (Post, Pre, M_{0})$ can be computed by solving the following ILP problem:

{\begin{matrix} min f (Post, Pre, M_{0}) = min {{\vec{1}}^{T} \cdot Post \cdot \vec{1} + {\vec{1}}^{T} \cdot Pre \cdot \vec{1} + {\vec{1}}^{T} \cdot M_{0}} \\ s . t . \begin{matrix} φ (E, D) \end{matrix} \end{matrix}

(6)

If some additional structural properties are known about the Petri net system, the corresponding constraints can be added to the above ILL problem in terms of the definition of the pre- and post-incidence matrices of the net. For example, if the Petri net does not contain any source place, i.e. $\forall p \in P$ , $• p \neq ϕ$ , the following constraint must be added: $P o s t \cdot {\overset{⇀}{1}}_{n \times 1} \geq {\overset{⇀}{1}}_{m \times 1}$ . Analogously, if the Petri net does not contain any sink place, i.e. $\forall p \in P$ , $p^{•} \neq ϕ$ , the following constraint must hold: $P r e \cdot {\overset{⇀}{1}}_{n \times 1} \geq {\overset{⇀}{1}}_{m \times 1}$ . If the Petri net does not contain any source transition, i.e. $\forall t \in T$ , $• t \neq ϕ$ , the following constraint must hold: $P r e^{T} \cdot {\overset{⇀}{1}}_{n \times 1} \geq {\overset{⇀}{1}}_{m \times 1}$ . If the Petri net does not contain any sink transition, i.e. $\forall t \in T$ , $t^{•} \neq ϕ$ , the following constraint must hold: $P o s t^{T} \cdot {\overset{⇀}{1}}_{m \times 1} \geq {\overset{⇀}{1}}_{n \times 1}$ .

Example 5. The modified unlabelled graph $G$ is considered in Figure 5. We want to determine a net system $(Σ, M_{0})$ with $Σ = (P, T, Pre, Post)$ and $m = 3$ , whose reachability graph is isomorphic to $G$ . In particular, we want to minimize the tokens in the initial marking and the arc weights. Moreover, we suppose that the target net system has no any source and sink node. The set of nodes is $Ω = {x_{0}, x_{1}, \dots, x_{6}}$ . By Algorithm 2 and Example 4, we know that the final partition of the nodes is: $Ω_{I} = {x_{0}}$ , $Ω_{ω 0} = {x_{5}, x_{6}}$ , $Ω_{ω 1} = {x_{3}, x_{4}}$ and $Ω_{ω 2} = {x_{1}, x_{2}}$ . The set of $ω$ -increasing production that ends in $x_{1}$ is $Δ_{↑}^{1} = {π_{1}}$ , with $l (π_{1}) = t_{1}$ . The set of $ω$ -decreasing production that ends in $x_{6}$ is $Δ_{↓}^{6} = {π_{6}}$ , with $l (π_{6}) = t_{3}$ . The set of $ω$ -stationary production that ends in $x_{1}$ is $Δ_{\to}^{1} = {π}$ , with $l (π) = t_{1} t_{2} t_{4} t_{2} t_{4}$ . The two productions, $π : x_{2} t_{3} x_{6}$ and $π' : x_{2} t_{4} x_{3} t_{2} x_{4} t_{4} x_{5} t_{2} x_{6}$ , are the equivalence productions.

The enabling set and the disabling set are shown as follows:

\begin{matrix} E = {(x_{0}, t_{1}), (x_{1}, t_{1}), (x_{1}, t_{2}), (x_{2}, t_{3}), (x_{2}, t_{4}), (x_{3}, t_{1}), \\ (x_{3}, t_{2}), (x_{4}, t_{3}), (x_{4}, t_{4}), (x_{5}, t_{1}), (x_{5}, t_{2}), (x_{6}, t_{3}), (x_{6}, t_{4})} \end{matrix}

\begin{matrix} D = {(x_{0}, t_{2}), (x_{0}, t_{3}), (x_{0}, t_{4}), (x_{1}, t_{3}), (x_{1}, t_{4}), (x_{2}, t_{1}), (x_{2}, t_{2}), \\ (x_{3}, t_{3}), (x_{3}, t_{4}), (x_{4}, t_{1}), (x_{4}, t_{2}), (x_{5}, t_{3}), (x_{5}, t_{4}), (x_{6}, t_{1}), (x_{6}, t_{2})} . \end{matrix}

We identify the net system in Figure 2(a) by solving the resulting ILP problem (Wolsey, 1998) with the file LINDO.

Conclusions

In this paper, we considered the problem of identifying a one-place unbounded Petri net system from its unlabelled modified coverability graph. The structure of an unbound Petri net model and the weight of the arcs cannot be identified from the coverability graph due to the loss of the information of $ω$ symbol. According to the modified coverability graph and the partition of the nodes in the corresponding unlabelled graph, a solution is provided to the problem of identifying a Petri net model whose modified coverability graph is isomorphic to the given unlabelled graph $G$ based on the solution of ILP problem.

Footnotes

Acknowledgements

The authors would like to thank the anonymous referees for their helpful comments and suggestions.

Funding

This work was supported by the National Nature Science Foundation of China (grant number 61273207).

References

Badouel

Darondeau

(1998) Theory of regions. Lecture Notes in Computer Science: Lectures on Petri Nets I: Basic Models. Berlin: Springer-Verlag, Vol. 1491, pp. 529–586.

Cabasino

Giua

Seatzu

(2006a) Identification of deterministic Petri nets. 8th International Workshop on Discrete Event Systems, Ann Arbor, MI, USA.

Cabasino

Giua

Seatzu

(2006b) Identification of unbounded Petri nets from their coverability graph. 45th IEEE International Conference on Decision and Control, San Diego, CA, USA.

Cabasino

Giua

Seatzu

(2007) Identification of Petri nets from knowledge of their language. Discrete Event Dynamical Systems: Theory and Application17: 447–474.

Ding

Jiang

Zhou

(2008) Deadlock checking for one-place unbounded Petri nets Based on modified reachability trees. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics38(3): 881–883.

Dotoli

Fanti

Mangini

(2008) Real time identification of discrete event systems using Petri nets. Automatica44(5): 1209–1219.

Estrada-Vargas

López-Mellado

Lesage

(2010) A comparative analysis of recent identification approaches for discrete event systems. Mathematical Problems in Engineering, 1–21.

Giua

Seatzu

(2005) Identification of free-labeled Petri nets via integer programming. 44th IEEE International Conference on Decision and Control and European Control Conference, Seville, Spain.

Giua

Corona

Seatzu

(2005) State estimation of free labeled Petri nets with contact-free nondeterministic transitions. Journal of Discrete Event Dynamic Systems15(1): 85–108.

10.

Giralt

Valk

(2003) Petri Nets for System Engineering: A Guide to Modeling, Verification, and Applications. Berlin: Springer, pp. 41–68.

11.

Hiraishi

(1992) Construction of a class of safe Petri nets by presenting firing sequences. Lecture Notes in Computer Science; 13th International Conference on Application and Theory of Petri Nets, Sheffield, UK. Berlin: Springer-Verlag, Vol. 616, pp. 244–262.

12.

Karp

Miller

(1969) Parallel program schemata. Journal Computer and System Sciences3(2): 147–195.

13.

Klein

(2005) Identification of discrete event systems for fault detection purposes. Ph.D. thesis, Ecole Normale Superieure de Cachan, Paris, France.

14.

Meda-Campaña

(2002) On-line identification of discrete event systems: fundamentals and algorithms for the synthesis of Petri net model. Ph.D. thesis, Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional, Unidad Guadalajara, Mexico.

15.

Peterson

(1981) Petri Net Theory and the Modeling of Systems. Englewood Cliffs, NJ: Prentice-Hall.

16.

Wang

Gao

Zhou

(2004) A modified reachability tree approach to analysis of unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics34(1): 303–308.

17.

Wang

Jiang

Jiao

(2010) Property checking for 1-place-unbounded Petri nets. 2010 Fourth International Symposium on Theoretical Aspects of Software Engineering.

18.

Wolsey

(1998) Integer Programming. New York: John Wiley & Son.