摘要
首先给出一个求取同时是极小死锁和陷阱的库所子集的多项式算法(简记为FDMST算法);之后提出了能在多项式时间内判断给定库所子集是否为S-不变量极小支集的RCMSD算法,当给定库所子集被判定为极小支集时,该算法能求得立于该支集上的一个S-不变量;最后将FDMST算法与RCMSD算法结合,提出了能在多项式时间复杂度内求取部分极小支集上S-不变量的STRC算法。
Firstly a polynomial algorithm FDMST is provided to derive some place subsets which are both minimal siphon and trap.After that,a polynomial algorithm RCMSD which can judge whether or not a given subset of places is a minimal support of S-invariants is presented.Once a minimal support is confirmed,RCMSD algorithm can derive one corresponding S-invariant simultaneously.Finally,combining RCMSD algorithm with FDMST algorithm,an algorithm STRC is presented which can compute some minimal-support S-invariants of Petri nets in Polynomial time.
出处
《系统仿真学报》
CAS
CSCD
北大核心
2008年第S2期29-32,共4页
Journal of System Simulation
基金
国家自然科学基金(60673053和60603090)
山东省优秀中青年科学家奖励基金(2006BS01019)
山东科技大学科学研究春蕾计划项目(2008BWZ027)
关键词
PETRI网
S-不变量
死锁
陷阱
STRC算法
Petri net
S-invariants
Siphon
Trap
Siphon_Trap
Rank_Cramer's rule based algorithm
