Mingming Yan (University of Electronic Science and Technology of China, China)

DOI: 10.4018/978-1-4666-4034-4.ch013

Chapter Preview

TopThe 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*, *M*_{0}) 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*, *M*_{0}) is bounded if ∃ *k*∈N, ∀*M*∈*R*(*N*, *M*_{0}), ∀ *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 *M*_{0} if ∀*M*∈*R*(*N*, *M*_{0}), ∃ M′∈*R*(*N*, *M*), M′(t> holds. (*N*, *M*_{0}) is deadlock-free if ∀ *M*∈*R*(*N*, *M*_{0}), ∃ *t*∈*T*, *M*(*t*〉 holds. (*N*, *M*_{0}) is live if ∀ *t*∈*T*, *t* is live under *M*_{0}.

A string *x*_{1}, *x*_{2}, …, *x*_{n} is called a path of *N* if and only if ∀ *i*∈{1,2,..., n-1}: *x _{i}*

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}*(

Search this Book:

Reset