The net unfolding technique reduces memory requirement, but the deadlock checking algorithms proposed are quite slow, even for medium-size unfoldings. It is known that the problem of deadlock checking a Petri net can be reduced to a mixed integer linear programming problem. In this paper, we present a development of this approach. We adopt Contejean-Devie's algorithm for solving systems of linear constraints over the natural numbers domain and refine it, 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 events involved in an unfolding, into a relationship between the corresponding integer variables in the system of linear constraints.
Experimental results demonstrate that the new technique achieves significant speedups.
The algorithm suffers from two problems, though. First one is the exponential running time while calculating event presets which can be reduced yet only for usual events. The second is the exponential growth of the prefix due to redundant branches created by tic events. In many cases this can be avoided if markings are compared using an equivalence relation while checking for cutoff events. With a careful definition the branches not needed for model checking are avoided while preserving a complete prefix in terms of reachability.