Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)

概要

論文の詳細を見る
A siphon-trap of a Petri net N is defined as a place set S with ^●S=S^●, where ^●S={u| N has an edge from u to a vertex of S} and S^● = {v| N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: 1. FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net; 2. FDST_i that repeats FDST i times in order to extract more minimal siphon-traps than FDST. 3. STFM_T (STFM_T_i, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDST_i) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.
社団法人電子情報通信学会の論文
2002-11-01