For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants
Akihiro TAGUCHI Atsushi IRIBOSHI Satoshi TAOKA Toshimasa WATANABE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/04/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
Petri nets, P-invariants, minimal supports, siphon-traps, Fourier-Motzkin method,
Full Text: PDF(225.2KB)
>>Buy this Article
A siphon-trap(ST) 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. A P-invariant is a |P|-dimensional vector Y with YtA = 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.