An algorithm for extracting minimal siphon-traps of Petri nets and its application to P-invariant computation

摘要

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|{sup}2(|P| + |T| + |E|)) time algorithm FDST that produces a maximal class of mutually disjoint minimal siphon-traps of a given Petri net, and its application to P-invariant computation is shown. An P-invariant of N is a |P|-dimensional vector Y with Y{sup}t. A = 0 for the place-transition incidence matrix A of N. Only nonnegative integer P-invariants are considered in this paper. Since any invariant is expressed as a linear combination of minimal-support P-invariants (ms-P-invariants for short) with nonnegative rational coefficients, we try to obtain some or all ms-P-invariants. As an application of FDST, we propose a fast algorithm STFM-T for computing one or more ms-P-invariants, and its usefulness is shown through experimental results.