摘要
活性是 Petri网的重要行为特征之一。为了得到判定 AC网活性有效的算法,本文利用分治的思想,在定义极小死锁的前、后归约子网的基础上,将较大问题分而治之,把未知问题转化为已知的FC网上的问题,从而得到了判定AC网活性及活性单调性的多项式时间的算法。
Liveness is one of the important behavioral properties of Petri nets. The aim of this contribution is to draw a more powerful algorithm to decide liveness of asymmetric choice nets （AC）. Firstly, this paper presents difinhions of Pre-induced subnet and Post-induced subnet of the minimal siphon. And then the idea of Divide and Conquer is introduced to transform the targeted problems into the counterpart of FC（free choice nets）. Finally, a polymial-time algorithm to decide liveness and liveness monotonichy of AC is presented.
出处
《计算机科学》
CSCD
北大核心
2005年第9期18-20,57,共4页
Computer Science
基金
国家自然科学基金(60073013)
国家重点基础研究专项经费(G1998030416)
中国科学院决策与信息系统实验室(MADIS)资助
四川省科技厅应用基础课题(03226125)
