Verification of Bounded Petri Nets Using Integer Programming

摘要

Model checking based on the causal partial order semantics of Petri nets is anapproach widely applied to cope with the state space explosion problem. One of the ways to exploit such a semantics is to consider (finite prefixes of ) net unfoldings-themselves a class acyclic Petri nets-which contain enough information, albeit implicit, to reason about the reachable markings of the original Petri nets. In (25), a verification technique for net unfoldings was proposed, in which deadlock detection was reduced to a mixed integer linear programming problem. In this paper, we present a further development of this approach. The essence of the proposed modifications is to transfer the information about causality and conflicts between the events involved in an unfolding, into a relationship between the corresponding integer variables in the system of linear constraints. Moreover, we present some problem-specific optimisation rules, reducing the search space.