A. Huck; J. Freiheit; A. Zimmermann: Convex Geometry Applied to Petri Nets: State Space Size Estimation and Calculation of Traps, Siphons, and Invariants.
Forschungsbericht 2000-6 des Fachbereichs Informatik der TU Berlin (technical report)
[ abstract ]

Abstract

The computation of Petri net properties - if solely based on its structural information - is less time and space consuming than methods based on a reachability graph analysis. In this paper we propose an improved algorithm for the generation of minimal invariants, traps, and siphons. Furthermore, a method for the efficient estimation of the state space size for Petri nets is presented, which uses the obtained structural properties. Both algorithms only require structural net information and are based on a new and improved implementation of the double description method. We show how this convex geometry technique can be successfully applied to Petri nets.