微信服务号

微信订阅号

2025-4-6- 20
Home > Archive>Volume 12, Issue 3, 2001 >340-346
PDF HTML XML Export Cite reminder
A Polynomial Time Judgement for Liveness of AsymmetricChoice Nets
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [14]
    • |
  • Related
    • |
  • 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．
    Related
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:3563
  • PDF: 4692
  • HTML: 0
  • Cited by: 0
History
  • Received:December 08,1999
  • Revised:April 25,2000
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033400Visitors
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