2.1. Petri Nets
The following theories are from (Ezpeleta, Colom & Martinez, 1995; Banaszak & Krogh, 1990; Barkaoui & Pradat-Peyre, 1996; Chu & Xie, 1997; Hsien & Chang, 1994; Zhou, Dicesare & Desrochers, 1992; Zhou & Dicesare, 1991; and Zhou, Dicesare & Rudolph, 1992).
A Petri net is a four-tuple N=(P, T, F, W) where P and T are finite and non-empty. P is the set of places and T is the set of transitions with P∪T≠Φ ; and P∩T=Φ. F⊆(P×T)∪(T×P) is called the flow relation or the set of directed arcs. W:F→ N is a mapping that assigns a weight to any arc, where N={0, 1, 2, …}. N=(P, T, F, W) is ordinary, denoted as N=(P, T, F), if ∀ f∈F, W(f)=1. Unless otherwise stated, we consider only ordinary Petri nets in this chapter. Incidence matrix (N) of net N is a |P|×|T| integer matrix and (N)(p, t)=W(t, p)-W(p, t). The preset of a node x∈P×T is defined as •x={y∈P∪T∣(y, x)∈F}. While the postset of a node x∈P∪T is defined as x•={y∈P∪T∣(x, y)∈F}. This notation can be extended to a set of nodes as follows: given X⊆P∪T, •X=∪x∈X•x and X•=∪x∈X x•. A marking is a mapping W:F→ N.
The pair (N, M0) is called a marked Petri net or a net system. The set of markings reachable from M in N is denoted as R(N, M). (N, M0) is bounded if ∃ k∈N, ∀M∈R(N, M0), ∀ p∈P, M(p)≤k holds. A transition t∈T is enabled under M, denoted by M(t〉, if ∀p∈•t: M(p)≥1. A transition t∈T is live under M0 if ∀M∈R(N, M0), ∃ M′∈R(N, M), M′(t> holds. (N, M0) is deadlock-free if ∀ M∈R(N, M0), ∃ t∈T, M(t〉 holds. (N, M0) is live if ∀ t∈T, t is live under M0.
A string x1, x2, …, xn is called a path of N if and only if ∀ i∈{1,2,..., n-1}: xi+1∈xi•, where ∀ x∈{x1, x2, …, xn}, x∈P∪T. A simple path from x1 to xn is denoted by SP(x1, xn). Petri net N is called a state machine if ∀ t∈T, |•t|=|t•|=1. A state machine component N′ = (P′, T′, F′, W′) of a Petri net N=(P, T, F, W) is a state machine and is a subnet of N consisting of places in P′, their presets and postsets, and related arcs. A Petri net is said to be state machine decomposable if it is covered by state machine components.
A nonempty set S⊆P is a siphon if •S⊆S• holds. A siphon is minimal if there is no siphon contained in S as a proper subset. A minimal siphon S is called a strict minimal siphon if •S ⊂ S•.
A P-vector is a column vector I: P→Z indexed by P, where Z is the set of integers. I is a P-invariant (place invariant) if I≠0 and I T(N)=0T. P-invariant I is said to be a P-semiflow if every element of I is non-negative. ||I||={p∈P∣I(p)≠0} is called the support of I. If I is a P-invariant of (N, M0) then ∀ M∈R(N, M0): ITM=ITM0. Siphon S is controlled by P-invariant I under M0 if ITM0 >0 and {p∈P∣I(p)>0}⊆S}. Such a siphon is called invariant-controlled.