# Liveness, Deadlock-Freeness, and Siphons

Kamel Barkaoui (CEDRIC-CNAM – Paris, France)
Copyright: © 2013 |Pages: 14
DOI: 10.4018/978-1-4666-3922-5.ch003

## Abstract

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
Top

## 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:
Reset