Liveness, Deadlock-Freeness, and Siphons

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 ∈(P∪T) is defined as ^•x = { y ∈ (P∪T) s.t. (y, x)∈F }, The postset of a node x ∈ (P∪T) is defined as x^• = { y∈(P∪T) 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 = ^•P ∪P^•; 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 p∈P is said to be non-blocking iff: p^• ≠ ∅ ⇒M in_t∈•p{V (t, p)} ≥ M in_t∈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 u∈F 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 ∈Z^P) is a P-invariant iff f ^t·C = 0^t. An integer vector g ≠ 0 indexed by T (g ∈Z^T) is a T-invariant iff C·g =0. || f ||={ p∈P/f (p) = 0} (resp. || g || = {t ∈ t/g(t) = 0}) is called the support of f (resp. of g). We denote by || f ||⁺={ p ∈ P/f (p) > 0} and by || f ||⁻= { p ∈ P/f (p) < 0}. N is said to be conservative iff there exists a P-invariant f such that || f || = || f ||⁺ = P.