Petri网信标和陷阱计算的矩阵半张量积方法

摘要

We address the problems of calculating siphons and traps in ordinary Petri nets (PNs) by resorting to the semi-tensor product (STP) of matrices. First, two matrix equations, called the siphon equation (SE) and trap equation (TE), respectively, are established by using STP. Second, it is proved that the problems of calculating all of the siphons and the traps in PNs are equivalent to solve all nonzero solutions of SE and TE, respectively. An algorithm is proposed to calculate all siphons and traps in PNs. Finally, an example and some experimental results are presented to illustrate the theoretical results and show that the proposed approach is more effective than the existing approach in calculating all siphons and traps in PNs. The proposed approach only requires matrix manipulations.%本文基于矩阵半张量积(semi-tensor product, STP)方法研究了普通Petri网(Petri nets, PNs)信标和陷阱的计算问题。首先,利用STP方法建立了两个矩阵方程,分别称为Petri网的信标方程(siphon equation, SE)和陷阱方程(trap equation, TE)。其次,证明了计算Petri网的信标和陷阱分别等价于求信标方程(SE)和陷阱方程(TE)的非零解。同时,给出了计算Petri网所有信标和陷阱的算法。最后,实例和实验结果说明了本文方法的可行性与有效性。本文所提出的方法对于Petri网信标和陷阱的计算是非常有效的,它只涉及到矩阵的乘法运算。