In: Lecture Notes in Computer Science, Vol. 1877: Concurrency Theory, Proceedings of CONCUR 2000, pages 410-425. Springer-Verlag, 2000.
Abstract: Model checking based on the causal partial order semantics of Petri nets is an approach 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 of acyclic Petri nets - which contain enough information, albeit implicit, to reason about the reachable markings of the original Petri nets. Melzer and Roehmer proposed a verification technique for net unfolding in which deadlock detection was reduced to a mixed integer programming problem. This paper presents a further development of this approach. Contejean-Devie's algorithm for solving systems of linear constraints over the natural numbers domain is adopted and refined by taking advantage of the specific properties of systems of linear constraints to be solved. The essence of the proposed modifications is to transfer the information about causality and conflicts between the corresponding integer variable in the system of linear constraints. Experimental results demonstrate that the new technique achieves significant speedups.
Keywords: LP deadlock checking, Petri nets, mixed integer programming, model checking, partial orders.