A fast and space-saving algorithm for computing invariants of Petri nets
M. Yamauchi, M. Wakuda, Satoshi Taoka, Takuo Watanabe · 2003
The paper proposes a new efficient algorithm STFM for finding one or more elementary invariants by combining the Fourier-Motzkin method and the minimal siphon extraction algorithm FDMS. The main point is that it tries to decrease the number of candidate vectors by restricting computation of invariants to place sets S or transition sets R such that /sup ./S=S/sup ./ (siphon and trap) or /sup ./R=R/sup ./, respectively. Experimental results are provided to show that incorporating this restriction into the Fourier-Motzkin method greatly reduces the maximum number of candidate vectors.