S-不变量求取的多项式算法  

A Polynomail Algorithm to Compute S-invariants

作　　者：鲁法明[1] 吴哲辉[1] 

机构地区：[1]山东科技大学信息科学与工程学院,青岛266510

出　　处：《系统仿真学报》2008年第S2期29-32,共4页Journal of System Simulation

基　　金：国家自然科学基金(60673053和60603090);山东省优秀中青年科学家奖励基金(2006BS01019);山东科技大学科学研究春蕾计划项目(2008BWZ027)

摘　　要：首先给出一个求取同时是极小死锁和陷阱的库所子集的多项式算法(简记为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.

关 键 词：PETRI网 S-不变量 死锁 陷阱 STRC算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]