Liveness and Boundedness of Decomposable Asymmetric Choice Nets
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [15]
  • |
  • Related [20]
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    Liveness and safeness are important behavioral properties of net systems. In this paper, a subclass of AC nets which are called decomposable asymmetric choice nets are obtained. A necessary and sufficient condition of liveness for decomposable AC systems is also proved. Moreover, a polynomial-time algorithm is presented to decide whether a Petri net system is live and bounded decomposable AC system.

    Reference
    [1] Murata, T. Petri nets: properties, analysis and applications. Proceedings of the IEEE, 1989,77(4):541~580.
    [2] Commoner, F., Holt, A.W., Even, S., et al. Marked directed graphs. Journal of Computer System Science, 1971,5(5):511~523.
    [3] Desel, J., Esparza, J. Free Choice Petri Nets. London: Cambridge University Press, 1995.
    [4] Barkaoui, K., Couvreur, J.M., Duteihet, C. On liveness in extended non self-controlling nets. Lecture Notes on Computer Science, 1995,935:25~44.
    [5] Kemper, P., Bause, F. An efficient polynomial-time algorithm to decide liveness and boundedness of free choice nets. Lecture Notes on Computer Science, 1992,616:263~278.
    [6] Barkaoui, K., Minoux, M. A polynomial time graph algorithm to decide liveness of some basic classes of bounded Petri nets. Lecture Notes on Computer Science, 1992,616:62~75.
    [7] McLeod, R.D., Kovalyov, A. Strongly connected free-choice systems having nondead home markings are live and bounded. Petri Net Newsletter, 1998,54:16~18.
    [8] Lu, Wei-ming, Zhen, Qiang. The study of petri net system liveness. Journal of Computer Science, 1999,26(4):1~4 (in Chinese).陆维明,甄强.Petri网活性与研究.计算机科学,1999,26(4):1~4.
    [9] Barkaoui, K., Pradat-Peyre, J. On liveness and controlled siphons in Petri nets. Lecture Notes on Computer Science, 1996,1091: 57~72.
    [10] Zhen, Qiang, Lu Wei-ming. On liveness and safeness of asymmetric choice nets. Journal of Software, 2000,11(5):590~605 (in Chinese).甄强,陆维明.论非对称选择网的活性与安全性.软件学报,2000,11(5):590~605.
    [11] Koutny, M. A compositional model of time Petri nets. Lecture Notes on Computer Science, 2000,1825:303~322.
    [12] Lakos, C. Composing abstraction of coloured Petri nets. Lecture Notes on Computer Science, 2000,1825:323~345.
    [13] Souissi, Y. On Liveness preservation by composition of nets via a set of places. In: Advances in Petri Nets. LNCS 524, 1991, 277~295.
    [14] He, K.X., Lemmon, M.D. Liveness verification of discrete event systems modeled by n-safe ordinary Petri nets. Lecture Notes on Computer Science, 2000,1825:227~243.
    [15] Ciardo, G., Luttgen, G., Siminiceanu, R. Efficient symbolic state-space construction for asynchronous systems. Lecture Notes on Computer Science, 2000,1825:103~122.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

徐静,陆维明.可分解非对称选择网的活性和有界性.软件学报,2002,13(11):2142-2148

Copy
Share
Article Metrics
  • Abstract:3296
  • PDF: 4836
  • HTML: 0
  • Cited by: 0
History
  • Received:January 18,2001
  • Revised:May 15,2001
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