S-不变量极小支集判定的多项式算法

A Polynomial Algorithm for the Decidability of Minimal Support of S-invariants

S-不变量是对Petri网进行结构性质分析的重要工具,但S-不变量的求取尚无有效算法。主要分析了S-不变量极小支集的判定问题。结合Petri网中库所子集列生成子阵的性质证明了一个库所子集为S-不变量极小支集的充分必要条件,在此基础上提出了判断给定库所子集是否为S-不变量极小支集的多项式算法。

The S-invariants play an important role in the structural property analysis of Petri nets even though there is no effective algorithm for the computation of S-invariants.This paper mainly discusses the decidability of minimal support of S-invariants.With a deep research of the property of derived matrix by place subset,a sufficient and necessary condition for a place subset to be a minimal support of S-invariants was proved firstly.And after that,a polynomial algorithm for the decidability of minimal suppor...