ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.3P.300-307



ۼȨѡĻ밲ȫ
ǿ½ά
ժҪ밲ȫϵͳҪΪ.λ/ǨϵͳһЩ࣬Ϊ֮Ľ.ĹΪһֳΪȨѡϵͳҵ밲ȫԵһ.ȸԵȼļҪֱ۵֤,,һలȫϵͳָԵĳֱҪ.
ؼʡȨѡ,,ȫ,ṹ,ṹȫ.
ͼšTP301
On Liveness and Safeness for Weighted Extended Free Choice Nets
ZHEN QiangLU Wei-ming
(Institute of Mathematics The Chinese Academy of Sciences Beijing100080)
AbstractLiveness and safeness are important behavioral properties of nets (systems).Many powerful results have been derived for some subclasses of Place/Transition nets (systems).The aim of this paper is to draw a general perspective of the liveness and safeness for a subclass with Extended Free Choice net-like underlying graph but allowing weights:Weighted Extended Free Choice nets (WEFC nets).First,a brief and intuitive proof of liveness equivalent condition for WEFC nets is given.Then,for safe nets,a sufficient and necessary condition is presented.
Key wordsWeighted extended free choice net,live,safe,structurally live,structurally safe.
Place/Transition net (P/T net)1 is a mathematical tool well suited for modelling and analyzing systems exhibiting behaviors such as concurrency,conflict and causal dependency between events.However,the high degree of complexity of the analysis limits the applicability of Petri nets to real-world problems.The reachability graph of such systems is actually unmanageable,thus it is crucial to enforce the analysis power of techniques based on the net structure.This paper presents new results in this direction.
Liveness and safeness are main behavioral properties of P/T nets.Liveness corresponds to the absence of global or local deadlock situations,safeness to the absence of overflows.Many results of liveness and safeness theory have been derived for restricted classes of P/T nets26,due to the use of some graph theoretic tools.We wondered how much it would change if we allow weights in the model.We consider the so-call WEFC nets (weighted extended free choice nets),that generalize the well known class of Extended Free Choice nets.In this paper,we first give an interesting simple proof to the liveness theorem (A WEFC net is live if and only if every subsystem generated by siphon is live).Then,for Safe WEFC nets,we give an equivalent condition.
The paper is organized as follows.The next section presents the basic concepts and notations.In section 2,the liveness for the WEFC nets is investigated.In section 3,we present a sufficient and necessary condition of (structure) liveness and (structure) safeness in WEFC nets.Section 4 concludes the paper.
1Basic Concepts
We assume the reader is familiar with the structure,firing rule and basic properties of net models7,and with elementary graph theory.However,in this section we recall some basic concepts and notations to be used.
Definition 1.1.
1.A (Petri) net is a triple N=(P,T;F) where
(1) P={p1,p2,...,pm} is a finite set of places,
(2) T={t1,t2,...,tn} is a finite set of transitions,
(3) F(PT)(TP) is a set of arcs (flow relation),
(4) PT= and PT,
(5) dom(F)cod(F)=PT(dom(F)={xy:(x,y)F},cod(F)={xy:(y,x)F}).
N=(P,T;F,W) is a weighted (Petri) net,where (P,T;F) is a (Petri) net,W:F{1,2,3,...} is a weight function.
2.A pair of a place p and a transition t is called a self-loop iff (p,t)F(t,p)F.A net is said to be pure iff it has no self-loops.
In the following,we'll only consider pure nets.
Definition 1.2.Let N=(P,T;F,W) be a weighted net.
1.The incidence matrix A of N is an mn matrix of integers and its entry is given by 

2.A net C is an elementary circuit iff it is connected and uP T:u=u=1.Since P=T=m1 here,we adopt the following notations:pi={ti} and ,W(ti,pi)=ci,iZ+ (Z+ is the set of nonzero positive integers),,where 1im, then 1 else i+1.The gain of an elementary circuit C is .C is neutral,absorbing or generating when the value of  equals,is less than or is greater than 1 respectively.
3.N=(P,T;F) is WSM (weighted state machine) iff tT:t=t=1.
4.N=(P,T;F) is weighted T-system iff pP:p=p=1.
5.N is WEFC net iff
(1) p1,p2P:p1p2p1=p2,
(2) pP,t1,t2p:W(p,t1)=W(p,t2).
6.A net N is strongly connected iff x,yPT,there exists a directed path from x to y.A net N is P-connected iff x,yP,there exists a directed path from x to y.
7.t1,t2T,t1 is called in structure conflict with t2 iff t1ɡt2.
Definition 1.3.
1.A net system is a 2-tuple =(N,M0) where
(1) N is a weighted net; (2) M0:P{0,1,2,3,...} is the initial marking.
2.The set of all markings reachable from M0 is called the reachability set and denoted by R(N,M0).
3.tT is live iff MR(N,M0),MR(N,M):t is enabled at M.
tT is dead iff t can never be fired at any MR(N,M0).
4.A place p in the preset of t is called enablingly marked iff M(p)W(p,t).
5.(N,M0) is safe iff kZ+,pP,MR(N,M0):M(p)k.(Safe is the recommended term in Net Community,sometimes it is called bounded).
N is structurally safe iff M0,(N,M0) is safe.
6.(N,M0) is live iff tT,t is live.
N is structurally live iff M0,(N,M0) is live.
N=(P,T;F) is a deadlock at marking M0 iff tT,t is dead.
7.Let =(N,M0) be a WEFC system.For pP,define  as follows:If p,then for tp, else 
Divide P into two subsets under any reachable marking MR(M0):

Property 1.1.
1.
2.If a siphon ,then N generated by H is a deadlock under M,i.e.,MR(N,M),tH,t is not enabled at M.
3.A WEFC system (N,M) is a deadlock pP:
In the following,MH,MH and ңH denote a marking of siphon H under system H that is generated by H,a marking of siphon H under system (N,M) and a firing sequence only including elements in H respectively.
2Liveness
In this section,we discussed the equivalent relation between a WEFC system and its subsystem generated by its siphon.References8,9 gave the same result for WFC nets (weighted free choice nets).Their proofs are different but both are very long and complicated.Here we give not only a proof for a larger class of WFC systems,WEFC systems,but also a quite simple proof for WEFC system in order to show some useful proof techniques.First,we introduce a lemma.
Lemma 2.1.Let =(P,T;F,W,M0) be a WEFC system and t be a transition of N.t is not live iff there exist a siphon H containing a place pʡt and a reachable marking M such that 
Proof.If such a siphon exists,t is obviously not live.
Now consider the necessary condition by recurrence on the number of transitions of the net.
If  is a system with only one transition,the lemma holds (If t is not live,one of its input places  and this place is a siphon).
Let  be a system with at least two transitions,t be a transition that is not live.As t is not live,there exists a reachable marking M such that t is dead under M.There are only two cases:
Case 1.In ,there exists another transition,u,that is not live.
By applying the recurrence hypothesis for transition u on the system (N{t},M),we obtain a marking M reachable from M and a siphon Hu,such that ,.Transitions t and u are dead for the system (N,M),so for any reachable marking of this system,we have 
By applying the recurrence hypothesis for transition t on the system (N{u},M),we obtain a marking M reachable from M and a siphon Ht,such that ,that contains a place in the preset of t.
Now HtHu is a siphon in (N,M0) which contains a place in the preset of t,and we have a marking MʣM0,such that 
Case 2.There exists no other transition in (N,M) that is not live.
Case 2.1.t is not in structure conflict with another transition.
Hence,each time a place p in the preset of t is enablingly marked,it remains enablingly marked until t fires.As t is dead under M,there must exist a place p in the preset of t such that p is never enablingly marked from M onward.If the preset of p contains no transition,the {p} is the siphon needed.Else,all the transitions in the preset of p are dead under MR(M).
Then it contradicts the assumption that only t is not live.
Case 2.2.t is in structure conflict with another transition v.
From the definition of WEFC net,v is not live under M,this contradicts the assumption.
That is the proof.

Theorem 2.1.If every subsystem generated by siphon in a WEFC system  is live,then the WEFC system  is live.
Proof.Assume  is not live,then there at least exists a transition t which is not live.From Lemma 2.1,there exist a siphon H containing a place pʡt and a reachable marking M such that .As firing of t (tTH) can't change the marking of H,the firing sequence ңH can be fired in H (H is the system generated by H).Now we have MH0ۦңHMH1 and .This contradicts the liveness of H.

Theorem 2.2.If a WEFC system is live,then every subsystem generated by sipnon is live.
Proof.Assume N=(P,T;F,W) is a WEFC net,system (N,M0) is live,but there exists a siphon HP such that subsystem =(N,M0) generated by H is not live,i.e.,there exists a transition t which is not live in .From Lemma 2.1,there exist a siphon H containing a place pʡt and a reachabele marking M1,such that ,M0ۦҡ䣾M1.As firing of t (tH䡤 but tH) can't change the marking of H and the firing sequence ҡH can be fired in H (H is the system generated by H).
Let ҡH=t1...tn (n0).If we can prove that there exists a ,such that M0ۦңM1 and ,there will be a contradiction with the liveness of .The theorem holds.
In the following,we will operate by recurrence on the number of n to prove the existence of  and M1.
Case 1.If n=0,then let =,M1=M0,the theorem holds.
Case 2.If n0,we have two subcases:
Case 2.1.Let uH be a transition enabled under M0 in H,hence u is enabled under M0 in H.Let pH and up={v1,...,vf} (if f=1,then v1=u),then there at least exists a transition ti{t1,...,tn} in {v1,...,vf}.Let ti be the first element of p,which first appears in ҡH.From the definition of WEFC net,we have ti(i-1j=1tj)= and can rewrite ҡH=tit1...ti-1ti+1...tn.Thus,we have M0tiM2t1...ti-1ti+1...tnM1,M0tiM2 and M2H=M2.
As n-1n,applying the recurrence hypothesis on M2,M2,t1...ti-1ti+1...tn,there exist 1 and M3 such that M2ۦ1M3 and .Let =ti1,M1=M3,the theorem holds.
Case 2.2.No transition in H is enabled under M0 in .
As  is live,let u be the first enabled transition in H under M2(M0ۦ1M2).Obviously,1H=.Hence we have M2H=M0.
Let pH and up={v1,...,vf},then there at least exists a transition ti{t1,...,tn} in {v1,...,vf}.Let ti be the first element of p,which first appears in ҡH.From the definition of WEFC net,we have ti(i-1j=1tj)= and can rewrite ңH=tit1...ti-1ti+1...tn.Thus,we have M0tiM2t1...ti-1ti+1...tnM1,M2tiM3 and M3H=M2.
As n-1n,applying the recurrence hypothesis on M3,M2,t1...ti-1ti+1...tn,there exist 2 and M4 such that M3ۦ2M4 and .Let =1ti2,M1=M4,the theorem holds.

From Theorem 2.1 and Theorem 2.2,we have the following theorem.
Theorem 2.3.A WEFC system is live iff every subsystem generated by sipnon is live.
Corollary 2.1.A WEFC system is live iff every subsystem generated by minimal sipnon is live.
Proof.The necessary condition is obvious.
Assume a WEFC system =(P,T;F,W,M0) is not live.From Lemma 2.1,there must exist a siphon H, and M0ۦңM such that .As in H,there at least exists a minimal siphon H,then .This contradicts the liveness of the subsystem generated by minimal siphon H.

Figure 1(a) shows that if every subsystem generated by the siphons {p1,p2,p3},{p1,p2,p4} is live,then the WEFC system is live.In Figure 1(b),as the subsystem generated by siphon {p1,p2,p3} or {p1,p2,p4} is not live,so the WEFC system is not live.

Fig.1
From now on,the liveness analysis of a WEFC system is much easier than before as it is enough to concentrate on the minimal siphon liveness only,which is a very small system analysis.
3Liveness and Safeness
Safeness in Petri nets is a very important and useful behavioral property and based on Petri nets,some international traffic safety standards are going to be made public.That is the motivation of this section.
Lemma 3.1.If a WEFC system =(P,T,F,W,M0) is live and safe,then pP,p must be included in a (minimal) siphon.
Proof.Let p be a place of P,such that p is not included in any (minimal) siphon.As  has no isolated place,p at least has one input transition tT (if p has no input transition, is not live) and pt.Let M1R(M0) and M1(p) be the maximal marking of p( is safe).
Consider marking M1,such that M1(p)=0 and M1(q)=M1(q) (qp).As every subsystem generated by (minimal) siphon is live under M1 (from Theorem 2.2),every subsystem generated by (minimal) siphon is live under M1.So,from Theorem 2.1,the WEFC system  is live under M.Therefore,we can reach a marking M2 such that M2(p)0.We can define M2(p)=M2(p)+M1(p) and M2(q)=M2(q) (qp).So M2R(M1),moreover,M2R(M0).But M2(p)M1(p),this is in contradiction with the safeness of p.The lemma holds.

In Fig.2,as p5 is not included in any siphon,firing t4 will increase the number of tokens consistently.So the WEFC system is unsafe.

Fig.2An unsafe but live WEFC system
Theorem 3.1.A WEFC system =(P,T,F,W,M0) is live and safe iff 
(i) every subsystem generated by siphon is live and safe; 
(ii) pP,p must be included in a siphon.
Proof.Assume the WEFC system is unsafe,then,there at least exists an unsafe place p.From (ii),we know p must be included in a siphon H (let MH0 be the initial marking of H,H be the subsystem generated by siphon H).
As H is safe,let K(p) be the upper bound of p.The WEFC system is unsafe,so there must exist a firing sequence  and M1 (M0ۦңM1),such that M1(p)K(p).
As firing of t (tTH) can't change the marking of H,the firing sequence ңH can be fired in H.Now we have MH0ۦңHMH1 and M1H=MH1,so MH1(p)K(p).This contradicts the safeness of H.So the WEFC system is safe.
From Theorem 2.1,the WEFC system is live.Sufficient conditions hold.
 From Theorem 2.2,every subsystem generated by siphon is live.
From Lemma 3.1,pP,p must be included in a siphon.
Let K(p) be the upper bound of p in .Assume there exists an unsafe subsystem H generated by siphon H,then from the liveness of ,there exists a firing sequence H=t1...tn such that tH:t{t1,...,tn},MH0ۦHMH1 and MH1(p)K(p).If we can prove that there exist a firing sequence  and marking M1,such that M0ۦңM1 and M1(p)K(p),there will be a contradiction with the safeness of .Safeness of every subsystem generated by siphon holds.
In the following,we will operate by recurrence on n to prove the existence of  and M1.
Case 1.If n=0,then let =,M1=M0,the safeness of subsystem holds.
Case 2.If n0,we have two subcases as follows:
Case 2.1.Let u (uH) be a transition enabled under M0 in ,hence,u is enabled under MH0 in H.Let pH and up={v1,...,vf} (if f=1,then v1=u).Let ti be the first element of p,which first appears in H.From the definition of WEFC net,we have ti(i-1j=1tj)= and can rewriteH=tit1...ti-1ti+1...tn.Thus,we have MH0tiMH2t1...ti-1ti+1...tnMH1,M0tiM2 and M2H=MH2.
As n-1n,applying the recurrence hypothesis on M2,MH2,t1...ti-1 ti+1...tn,there exist 1 and M3 such that M2ۦ1M3 and M3(p)K(p).Let =ti1,M1=M3,the safeness of subsystem holds.
Case 2.2.No transition in H is enabled under M0 in .
As  is live,we can let u be the first enabled transition in H under M2(M0ۦ1M2).Obviously,1H=.Hence we have M2H=MH0.This transforms to Case 2.1.Safeness of subsystem holds.

Theorem 3.2.A WEFC system =(P,T,F,W,M0) is live and safe iff 
(i) every subsystem generated by minimal siphon is live and safe;
(ii) pP,p must be included in a minimal siphon.
Proof. Follow Theorem 3.1 and Lemma 3.1.
 Assume the WEFC system is unsafe,then,there at least exists an unsafe place p.From (ii),p must be included in a minimal siphon H (let M0H be the initial marking of H,H be the subsystem generated by minimal siphon H).As H is safe,we let K(p) be the upper bound of p.The WEFC system is unsafe,so there must exist a firing sequence  and M1 (M0ۦңM1.
As firing of t (tT H) can't change the marking of H,the firing sequence ңH can be fired in H.Having MH0ۦңHMH1 and M1H=MH1 must have MH1(p)K(p).This contradicts the safeness of H.So the WEFC system is safe.
From Corollary 2.1,we know the WEFC system is live.Sufficient conditions hold.

From Theorem 3.1 and Theorem 3.2,we have the following corollary.
Corollary 3.1.A WEFC net N=(P,T;F,W) is structurally live and structurally safe iff
(i) every subsystem generated by (minimal) siphon is structurally live and structurally safe;
(ii) pP,p must be included in a (minimal) siphon.
From Corollary 3.1,the structure liveness and structure safeness of WEFC net transform to the structure liveness and structure safeness of minimal siphon,which is very small net structure analysis.
Lemma 3.2.H is a minimal siphon in WEFC net iff (a) H is P-connected,(b) tH,tH=1.
Note:In 7,this lemma is for the WFC net.By the same method,we can have this lemma.
Lemma 3.3.Let H be a minimal siphon in the WEFC net.If H is live under M,then MiM H is live under Mi.
Proof.From Ref.8,we have the above conclusion for the WFC net.As H is a WFC net,Lemma 3.3 holds.

Lemma 3.4.8 Every elementary circuit C is structurally live iff C is neutral or generating.
Lemma 3.5.9 If a connected Petri net system (N,M0) is live and safe,then N is strongly connected.
Lemma 3.6.10 Let (N,M0) be a live Weighted T-system.If M0M0 then (N,M0) is live.
Lemma 3.7.7 A place p in a Petri net N is structurally unsafe iff there exists an n-vector X of nonnegative integers such that ,where the pth entry of M0 (i.e.,M(p)0).
Proposition 3.1.Let N=(P,T;F,W) be a weighted net.If N is strongly connected,then any xPT must be included in some elementary circuits.
Theorem 3.3.Let H be a minimal siphon in the WEFC net.If H is structurally live and structurally safe,then every elementary circuit must be neutral or absorbing.
Proof.Assume there exists an elementary circuit C(t0p0...tnpnt0) such that  and let AC be the incident matrix of C.Now we only concentrate on the analysis of C.Let an n-vector ,then we have ,.As ,therefore .Because AC and  is a vector of nonnegative integers,from Lemma 3.7,we know C is structuraly unsafe.Therefore,there exist a marking MC of C,a firing sequence C and a ,such that MCۦCMC and  is any bound of p).As H is live,there exists a living marking MH.Define marking MH,such that pH MH(p)=MH(p) (if pC and MC(p)MH(p) or p is not included in C),MH(p)=MC(p) (if pC and MC(p)MH(p)).From Lemma 3.3,H is live under MH.As H is structurally safe, must have an upper bound .As H is a minimal siphon in WEFC net,from Lemma 3.2,we have tH,tH=1.Therefore,the firing sequence C can be fired in subsystem H and we have MHۦCMH such that .This contradicts the safeness of .Theorem 3.3 holds.

Theorem 3.4.Let H be a minimal siphon in the WEFC net,H be the subsystem generated by H and every elementary circuit is neutral.If H is a structurally live and structurally safe,then H is a structurally live,structurally safe and strongly connected WSM.
Proof.As H is structurally safe and structurally live,from Lemma 3.5,H is strongly connected.
As H is a minimal siphon,from Lemma 3.2,we have tH,tH=1.
Assume there exists a transition tH such that t1.Let t={p1,...,pm} (p1,...,pmH).From Proposition 3.1,we know t must be included in an elementary circuit C and let p1C.As ,from Lemma 3.4,C is structurally live.Therefore,there exists a living marking MC of C.As H is live,there exists a living marking MH.Define marking MH,such that pH MH(p)=MH(p) (if pC and MC(p)MH(p) or p is not included in C),MH(p)=MC(p) (if pC and MC(p)MH(p)).From Lemma 3.3,H is live under MH.From Lemma 3.6,C is live under MH.We can only fire transitions in C and firing t will consistently increase the marking of p2,...,pm.This contradicts the safeness of H.So tH,tH=1.Thus,H is a structurally live,structurally safe and strongly connected WSM.
In Figure 3(a),the minimal siphon is a structurally live and safe WSM,so the minimal siphon is structurally live and safe.But in Figure 3(b),t21,therefore the minimal siphon is structurally unsafe.

Fig.3Tow minimal siphons in WEFC net
So for a minimal siphon in which every elementary circuit is neutral,the problem of structure liveness and safeness is transformed to structure liveness and safeness of WSM in which every elementary circuit is neutral.Here we'll not discuss neutral WSM in detail.In case of existing absorbing circuits in the minimal siphon,the problem will be very complicated,i.e.,further discussion is needed.
4Conclusion
We present a quite simple proof of liveness equivalent condition for WEFC nets.Then,for safe WEFC nets,a sufficient and necessary condition is presented.We conjecture the living problem for safe WEFC nets can be decided in polynomial time,which is a real challenging problem to attract further study.
This research is supported by the National Natural Science Foundation of China(Ȼѧ,No.69773016),the Laboratory of Management,Decisionn and Information System of the Chinese Academy of Sciences(MIDIS)of China(йѧԺϢϵͳʵ,No.H8902),and the National Grand Foundational Research Project of China(صоר,No.973002).ZHEN Qiang was born in 11968.He received a Ph.D.degree in comprter science from the Chinese Academy of Sciences in 1998.His research interests are Petri nets and communications.LU Wei-ming was born in 1941.He is a professor and doctoral supervisor of the Institute of Mathematics,the Chinese Academy of Sciences.His current research areas include Petri nets,algorithm and software technology.
Manuscript received 1997-10-21,accepted 1998-09-09
ߵλ:ǿ(йѧԺѧо100080)
½ά(йѧԺѧо100080)
References
1Reisig W.Petri nets,an introduction.Berlin:Springer-Verlag,1985
2Commoner F,Holt A W,Even S et al.Marked directed graphs.Journal of Computer System Science,1971,5:511523
3Hack M.Analysis of production schemata by Petri netsM S Thesis.Department of Electrical Engineering,Cambridge,Mass:MIT,1972
4Esparza J,Silva M.A polynomial-time algorithm to decide liveness of safe free-choice nets.Journal of Theoretical Computer Science,1992,102:185205
5Barkaoui K,Couvreur J M,Duteilhet C.On Liveness in extended non-self-controlling nets.LNCS,1995,935:2544
6Kemper P,Bause F.An efficient polynomial-time algorithm to decide liveness and safeness of free-choice nets.LNCS,1992,616:263278
7Murata T.Petri Nets:Properties,analysis and applications.Proceedings of the IEEE,1989,77(4):541580
8Xie X.On liveness of weighted free choice netsM S Thesis.Institute of Mathematics,The Chinese Academy of Sciences,1996
(л͵.ۼȨѡĻԣ˶ʿѧλģ.йѧԺѧо1996)
9Cao C.Liveness characterization for GFC systems (I) (II).Science in China (Series E),1996,39(33):196216
10Teruel E,Chrzastowski P,Colom J M et al.On weighted T-systems.LNCS,1992,616:348366
