基于T-不变量的可重复向量的求解算法

T-invariant based Methods for Computing Repetitive Vectors of Petri Nets

研究了Petri网中T-不变量与可重复向量之间的关系,并基于此关系给出一个求解可重复向量的新方法。首先定义了变迁扩充网的概念,证明一个网的可重复向量与其变迁扩充网的T-不变量之间存在一一对应关系,从而将一个网可重复向量的求解转换为其变迁扩充网T-不变量的求解上。在此方法中,如果利用FM-算法去求解T-不变量,则某些求解的步骤可以省略,从而得到一个类似于FM-算法的算法来求解可重复向量。此算法能够求出一组可重复向量,而任一可重复向量都可被这组可重复向量非负有理系数线性表出。

In this paper, the relation among T-invariants and repetitive vectors is investigated and new method for computing repetitive vectors is suggested based on them. The transition-added net of a net is defined and a relation is shown that there always exists a T-invariant of the transition-added net corresponding to a repetitive vector of the original net, and vice versa. Based on this relation, a general algorithm that can compute a set of repetitive vectors of a net is presented. It is proved that any repetitive vector of a net can be expressed as a linear combination of these repetitive vectors with nonnegative rational coefficients. Finally, based on FM-algorithm for computing T-invariants, another algorithm, which is similar to FM-algorithm, is described for computing repetitive vectors.