微信服务号

微信订阅号

2025年4月25日 4:23 星期五
首页 > 过刊浏览>2001年第12卷第3期 >340-346
PDF HTML阅读 XML下载 导出引用 引用提醒
非对称选择网活性的一个多项式时间判定
作者:
基金项目:

This project is supported by the National natural Science Foundation of China under Grant No.69773016 （国家自然科学基金）and the National Key fundamental Research Program of China under Grant No。G1998030416（国家重点基础研究专项经费）.


A Polynomial Time Judgement for Liveness of AsymmetricChoice Nets
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [14]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    活性判定是Petri网中一直没有完全解决的问题．针对非对称选择网的活性问题，利用结构分析理论，作了进一步的研究．首先，讨论和分析了活性判定的一般方法，然后利用S－不变，提出了非对称选择网活性判定的一个充分条件，并给出了相应的多项式算法．同时，对有界的非对称选择网的活性单调性问题进行了深入的研究，得到了一个简单的充分必要条件

    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．

    参考文献
    [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．
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:3569
  • 下载次数: 4709
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1999-12-08
  • 最后修改日期:2000-04-25
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19868341位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号