Efficient computation of enabled transition bindings in high-level Petri nets

Abstract

We present an algorithm for the computation of enabled transition bindings in high-level Petri nets. The algorithm does not depend on either functional or logic language features, but may be implemented in commonly used imperative languages. To achieve this we show that a high-level Petri net transition, together with its input arcs, input places and place markings, constitutes an extended type of finite domain Constraint Satisfaction Problem. Calculation of all transition bindings corresponds to solving such a problem, which we term a resource-value CSP. We show how the use of multi-sets in net markings and arc expressions leads to resource constraints. We describe the extension of an existing efficient CSP algorithm to enable solution of resource-value CSPs. The new algorithm, FC-CBJ-M, has been used for the simulation and analysis of Coloured and PrT nets.