Efficient calculation of Petri net invariants by the Fourier-Motzkin method

摘要

An invariant of a Petri net N = (P, T, F, α, β) is a |T|-dimensional vector X (a T-invariant) with A·X = 0{top}- (zero vector) or a │P│-dimensional vector Y (a P-invariant) with Y{sup}t·A = 0{top}- for the place-transition incidence matrix A of N. The Fourier-Motzkin (FM) method is well-known for computing all such nonnegative integer invariants. This method, however, has a critical deficiency: no outputs may he given even if invariants exist because of memory overflow in storing intermediary vectors which are candidates for invariants. In order to overcome this deficiency, several ideas to decrease the number of candidate vectors have been proposed. The subject of the paper is to show how to execute FM method efficiently in calculating nonnegative integer invariants. First, appropriate orderling in processing transitions is given. Secondly, a method for deleting candidate vectors and its correctness proof are given. Finally it is experimentally evaluated that these methods incorporated in FM method greatly improve the quality of solutions and reduce the computation time as well as memory size required.