Create a Free IGI Global Library Account to Receive a 25% Discount on All Purchases

Exclusive benefits include one-click shopping, flexible payment options, free COUNTER 4 and MARC records, and a 25% discount on all titles as well as the award-winning InfoSci^{®}-Databases.

InfoSci^{®}-Journals Annual Subscription Price for New Customers: As Low As US$ 4,950

This collection of over 175 e-journals offers unlimited access to highly-cited, forward-thinking content in full-text PDF and XML with no DRM. There are no platform or maintenance fees and a guarantee of no more than 5% increase annually.

Encyclopedia of Information Science and Technology, Fourth Edition (10 Volumes) Extended Offer

Receive the complimentary e-books for the first, second, and third editions with the purchase of the Encyclopedia of Information Science and Technology, Fourth Edition e-book. Plus, take 20% off when purchasing directly through IGI Global's Online Bookstore.

Barkaoui, K. (2013). Liveness, Deadlock-Freeness, and Siphons. In M. Khalgui, O. Mosbahi, & A. Valentini (Eds.), Embedded Computing Systems: Applications, Optimization, and Advanced Design (pp. 65-78). Hershey, PA: IGI Global. doi:10.4018/978-1-4666-3922-5.ch003

Chicago

Barkaoui, Kamel. "Liveness, Deadlock-Freeness, and Siphons." In Embedded Computing Systems: Applications, Optimization, and Advanced Design, ed. Mohamed Khalgui, Olfa Mosbahi and Antonio Valentini, 65-78 (2013), accessed February 24, 2018. doi:10.4018/978-1-4666-3922-5.ch003

Download link provided immediately after order completion

$30.00

List Price: $37.50

Current Promotions:

Take 20% Off All Publications Purchased Directly Through the IGI Global Online Bookstore: www.igi-global.com/

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.

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 ∈(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.