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 it to a place of S if and only if there is an edge from a place of S to it. In this paper, we propose an O(|P|{sup}2(|P|+|T|+|E|)) time algorithm GMST and another one GMST{sub}i that repearts GMST{sub}i times. By incorporating GMST{sub}i into the Fourier-Motzkin method as preprocessing, we propose an algorithm STFM_G for computing minimal-support nonnegative integer invariants. It is shown, through experimental results, that GMST, can extract more minimal siphon-traps and is faster than existing algorithms and that STFM_G has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.