A siphon-trap(S T) of a Petri net N = (P, T, E, α,β) is defined as a set 5 of places such that, for any transition t, there is an edge from t to a place of S if and only if there is an edge from a place of S to t. A P-invariant is a ∣P∣-dimensional vector Y with Y~t · A = 0 for the place-transition incidence matrix A of N. The Fourier-Motzkin method is well-known for computing all such invariants. This method, however, has a critical deficiency such that, even if a given Perti net N has any invariant, it is likely that no invariants are output because of memory overflow in storing intermediary vectors as candidates for invariants. In this paper, we propose an algorithm STFM_N for computing minimal-support nonnegative integer invariants: it tries to decrease the number of such candidate vectors in order to overcome this deficiency, by restricting computation of invariants to siphon-traps. It is shown, through experimental results, that STFM_N has high possibility of finding, if any, more minimal-support nonnegative integer invariants than any existing algorithm.
展开▼
机译：Petri 网 N = （P， T， E， α，β） 的虹吸阱 （S T） 定义为一组 5 个位置，使得对于任何过渡 t，当且仅当存在从 S 位置到 t 的边时，存在从 t 到 S 位置的边。P 不变量是 ∣P∣ 维向量 Y，其中 Y~t ·N 的位置转移入射矩阵 A = 0。傅里叶-莫茨金方法以计算所有这些不变量而闻名。然而，这种方法有一个严重的缺陷，即即使给定的 Perti net N 具有任何不变量，也可能由于在存储中间向量作为不变量的候选对象时内存溢出而没有输出不变量。在本文中，我们提出了一种STFM_N计算最小支持非负整数不变量的算法：它试图通过将不变量的计算限制为虹吸陷阱来减少此类候选向量的数量以克服这一缺陷。通过实验结果表明，STFM_N很有可能找到比任何现有算法更多的最小支持非负整数不变量（如果有的话）。
展开▼
