An algorithm GMST for extracting minimal siphon-traps and its application to efficient computation of Petri net invariants

A siphon-trap of a Petri net N = (P, T, E, α, β) is defined as a set S 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. In this paper, we propose an O(|P|²(|P| + |T| + |E|)) time algorithm GMST and another one GMST_i that repeats GMST i times. By incorporating GMST_i into the Fourier-Motzkin method as preprocessing, we propose an algorithm STFM_G_i for computing minimal-support nonnegative integer invariants. It is shown, through experimental results, that GMST_i can extract more minimal siphon-traps and is faster than existing algorithms and that STFM_G_i has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.