非对称选择网活性的一个多项式时间判定
作者:
基金项目:

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
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [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

复制
分享
文章指标
  • 点击次数:3559
  • 下载次数: 4691
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:1999-12-08
  • 最后修改日期:2000-04-25
文章二维码
您是第19783460位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号