On liveness and boundedness of asymmetric choice nets

doi:10.1016/S0304-3975(03)00359-1

CSpace

	On liveness and boundedness of asymmetric choice nets
	Jiao, L ; Cheung, TY ; Lu, WM
	2004-01-23
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	311 期号:1-3 页码:165-197
摘要	This paper concerns two important techniques, characterization and property-preserving transformation, for verifying some basic properties of asymmetric choice Petri nets (AC nets). In the literature, a majority of the characterizations are for ordinary free choice nets. This paper presents many extended (from free choice nets) and new characterizations for four properties: liveness with respect to an initial marking, liveness monotonicity with respect to an initial marking, well-formedness, liveness and boundedness with respect to an initial marking. The nets involved are extended to homogeneous free choice nets, ordinary AC nets and homogeneous AC nets. This paper also investigates the transformation of merging a set of places of an ordinary AC net and proposes the conditions for it to preserve the siphon-trap-property (ST-property), liveness, boundedness and reversibility. The results are then applied to the verification of resource-sharing systems. At present, the major approaches for solving this problem are based on state machines or marked graphs and are not based on property preservation. Our approach extends the scopes of the underlying nets to AC nets and the verification techniques. It is found that the ST-property plays a very important role in many of the results. Furthermore, mainly through examples, the importance of the assumptions in the proposed characterizations and transformation and the limitation on further extensions are pointed out. (C) 2003 Elsevier B.V. All rights reserved.
关键词	analysis asymmetric choice nets characterization liveness and boundedness well-formedness theory of Petri nets
DOI	10.1016/S0304-3975(03)00359-1
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000188499200005
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/582
专题	中国科学院数学与系统科学研究院
通讯作者	Jiao, L
作者单位	1.City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China 2.Chinese Acad Sci, Inst Software, Beijing 100864, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100864, Peoples R China
推荐引用方式 GB/T 7714	Jiao, L,Cheung, TY,Lu, WM. On liveness and boundedness of asymmetric choice nets[J]. THEORETICAL COMPUTER SCIENCE,2004,311(1-3):165-197.
APA	Jiao, L,Cheung, TY,&Lu, WM.(2004).On liveness and boundedness of asymmetric choice nets.THEORETICAL COMPUTER SCIENCE,311(1-3),165-197.
MLA	Jiao, L,et al."On liveness and boundedness of asymmetric choice nets".THEORETICAL COMPUTER SCIENCE 311.1-3(2004):165-197.