Finding Stubborn Sets of Coloured Petri Nets without Unfolding

A lower bound result is given stating that there exist CP-nets for which computing "good" stubborn sets requires time proportional to the size of the equivalent PT-net, and an approximative method is suggested which does not rely on unfolding.

Abstract

In this paper, we address the issue of using the stubborn set method for Coloured Petri Nets (CP-nets) without relying on unfolding to the equivalent Place/Transition Net (PT-net). We give a lower bound result stating that there exist CP-nets for which computing "good" stubborn sets requires time proportional to the size of the equivalent PT-net. We suggest an approximative method for computing stubborn set of process-partitioned CP-nets which does not rely on unfolding. The underlying idea is to add some structure to the CP-net, which can be exploited during the stubborn set construction to avoid the unfolding. We demonstrate the practical applicability of the method with both theoretical and experimental case studies, in which reduction of the state space as well as savings in time are obtained.