Liveness, Deadlock-Freeness, and Siphons

Liveness, Deadlock-Freeness, and Siphons

Kamel Barkaoui (CEDRIC-CNAM – Paris, France)
DOI: 10.4018/978-1-4666-3922-5.ch003


This chapter deals with the structure theory of Petri nets. The authors define the class of P/T systems, namely K-systems, for which the equivalence between controlled-siphon, deadlock-freeness, and liveness properties holds. Using the new structural notions of ordered transitions and root places, they revisit the non-liveness characterization of P/T systems satisfying the cs-property and define by syntactical manner new and more expressive subclasses of K-systems where the interplay between conflict and synchronization is relaxed.
Chapter Preview

2. Basic Definitions And Notations

This section contains the basic definitions and notations of Petri nets’ theory (Reisig, 1985) which will be needed in the rest of this chapter.

2.1. Place/Transition Nets

  • Definition 1:A P/T net is a weighted bipartite digraph N =(P, T, F, V) where: P ≠ ∅ is a finite set of node places; T ≠ ∅ is a finite set of node transitions; F ⊆ (P × T) ∪ (T × P) is the flow relation; V: F → IN+is the weight function (valuation).

  • Definition 2:Let N = (P, T, F, V) be a P/T net. The preset of a node x ∈(PT) is defined as x = { y ∈ (PT) s.t. (y, x)∈F }, The postset of a node x ∈ (PT) is defined as x = { y∈(PT) s.t. (x, y)∈F}, the preset (resp. postset) of a set of nodes is the union of the preset (resp. postset) of its elements. The sub-net induced by a sub-set of places P’P is the net N’= (P’, T’, F’, V’) defined as follows: T = PP; F = F ∩ ((P × T)∪(T × P)); V is the restriction of V on F’. The sub-net induced by a sub-set of transitions T’T is defined analogously.

  • Definition 3:Let N =(P, T, F, V) be a P/T net. A shared place p (|p|≥2) is said to be homogenous iff:t, t’p, V(p, t) = V (p, t’). A place pP is said to be non-blocking iff: p ≠ ∅M int∈•p{V (t, p)} ≥ M int∈p• {V (p, t)}. If all shared places of P are homogenous, then the valuation V is said to be homogenous. The valuation V of a P/T net N can be extended to the application W from (P × T)∪(T × P) IN defined by:u∈(P × T)∪ (T × P), W (u)=V(u) if uF and W (u)=0 otherwise.

  • Definition 4:The matrix C indexed by P ×T and defined by C(p, t) = W(t, p) − W(p, t) is called the incidence matrix of the net. An integer vector f ≠ 0 indexed by P (f ∈ZP) is a P-invariant iff f t·C = 0t. An integer vector g ≠ 0 indexed by T (gZT) is a T-invariant iff C·g =0. || f ||={ pP/f (p) = 0} (resp. || g || = {tt/g(t) = 0}) is called the support of f (resp. of g). We denote by || f ||+={ pP/f (p) > 0} and by || f ||= { pP/f (p) < 0}. N is said to be conservative iff there exists a P-invariant f such that || f || = || f ||+ = P.

Complete Chapter List

Search this Book: