摘要： 用于计算Petri网S不变量的M-S算法将所有正负行两两做线性组合变换，增加了算法的复杂度，得到的最终结果也并不一定是最小S不变量支撑。针对该问题，提出一种改进算法。通过增加对Petri网关联矩阵的预处理步骤，减少线性组合运算的次数，并得到最小S不变量支撑。理论与实验结果证明，M-S算法的复杂度为s×t，而改进算法的复杂度为s＋t，该算法能有效减少计算复杂度。

关键词: Petri网, S不变量, 状态方程, 复杂度

Abstract: An improved and efficient algorithm is brought up for M-S algorithm computing s-invariants of petri 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.

Key words: Petri nets, S-invariants, equation of state, complexity

中图分类号: 

• TP311.52