A Polynomial Time Judgement for Liveness of AsymmetricChoice Nets
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [14]
  • |
  • Related [20]
  • |
  • Cited by [1]
  • | |
  • Comments
    Abstract:

    The problem on liveness judgementis stillopen in Petrinets.The paper studies liveness on Asym-metric Choice nets(AC nets)by structure analysis theory.Firstly,some known results on liveness are dis-cussed.Then a sufficient condition by S-invariant for the liveness ofACnets is presented and the correspondingpolynomial-time algorithm is got.Finally a simple necessary-and-sufficientcondition on monotonicity ofboundedACnets is presented.

    Reference
    [1] Reisig,W.Petri Nets,An Introduction.Berlin:Springer-Verlag,1985.
    [2] Esparza,J.,Silva,M.A polynomial-time algorithm to decide liveness of bounded free-choice nets.Journal of Theoretical  Computer Science,1992,102:185~205.
    [3] Barkaoui,K.,Minoux,M.A polynomial-time graph algorithm to decide liveness of some classes of bounded Petri nets.  LNCS,1992,616:62~75.
    [4] Lautenbach,K.,Ridder,H.Liveness in bounded Petri nets which are covered by T-invariants.LNCS,1994,815:358~  375.
    [5] Kemper,P.,Bause,F.An efficient polynomial-time algorithm to decide liveness and boundedness of free-choice nets.  LNCS,1992,616:263~278.
    [6] Desel,J.A proof of the rank theory for extended free choice nets.LNCS,1992,616:134~153.
    [7] Barkaoui,K.,Couvreur,J.M.,Duteilhet,C.On liveness in extended non self-controlling nets.LNCS,1995,935:23~  44.
    [8] Minoux,M.,Barkaoui,K.Polynomialtime algorithms for proving or disproving commoner's structural property in Petrinets.In:Simpson,D.ed.Proceedings of the 9th International Conference on Application and Theory of Petri Nets. Venice Italy:IBM Deutschland,1988.
    [9] Murata,T.Petri nets,properties,analysis and applications.In:Proceedings of the IEEE,1989,77(4):541~580.
    [10] Lu,W.,Zhen,Q.Research for the liveness of Petri net systems.Chinese Journal of Computers,1999,22(4):1~4(in  Chinese).陆维明,甄强.Petri网系统活性的研究.计算机学报,1999,22(4):1~4.
    [11] Zhen,Q.,Lu,W.On liveness and safeness of asymmetric choice nets.Journal of Software,2000,11(5):590~605(in  Chinese).甄强,陆维明.论加权扩充自由选择网的活性和安全性.软件学报,2000,11(5):590~605.
    [12] Zhen,Q.On liveness and boundedness of asymmetric choice nets[Ph.D.Thesis].Institute of Mathematics,The Chinese  Academy of Sciences,1998.
    [13] Zhen,Q.,Lu,W.On liveness of asymmetric choice nets.Journal of Software,1998,9(5):354~359(in Chinese).
    [14] Barkaoui,K.,Pradat-Peyre,J-F.On liveness and controlled siphons in Petrinets.LNCS,1996,1091:57~72.甄强,陆维明.论非对称选择网的活性.软件学报,1998,9(5):354~359.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

焦莉,陆维明.非对称选择网活性的一个多项式时间判定.软件学报,2001,12(3):340-346

Copy
Share
Article Metrics
  • Abstract:3560
  • PDF: 4691
  • HTML: 0
  • Cited by: 0
History
  • Received:December 08,1999
  • Revised:April 25,2000
You are the first2032800Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063