一种改进的Petri网S不变量计算方法  

Improved Computing Method for S-invariants of Petri Nets

作　　者：周丰[1] 王明哲[1] 王莉[1] 

机构地区：[1]华中科技大学控制科学与工程系,武汉430074

出　　处：《计算机工程》2010年第17期1-3,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60874068)

摘　　要：用于计算Petri网S不变量的M-S算法将所有正负行两两做线性组合变换,增加了算法的复杂度,得到的最终结果也并不一定是最小S不变量支撑。针对该问题,提出一种改进算法。通过增加对Petri网关联矩阵的预处理步骤,减少线性组合运算的次数,并得到最小S不变量支撑。理论与实验结果证明,M-S算法的复杂度为s×t,而改进算法的复杂度为s+t,该算法能有效减少计算复杂度。An improved and efficient algorithm is brought up for M-S algorithm computing s-invariants ofpetri nets. The M-S algorithm executes the linear combination between all the positive lines and negative lines, which increases the complexity of the algorithm and the result maybe not the largest linearly independent set, so the final result is not always the minimal support S-invariants. Improved algorithm proposed in this paper increases the pre-processing of the flow matrix, which significantly reduces the number of linear combination operations, and the final results are minimal support S-invariants. It is theoretical proved that the complexity of the original algorithm is s ×t and the improved algorithm complexity is s＋t, the complexity is effectively reduced.

关 键 词：PETRI网 S不变量 状态方程 复杂度 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]