Toggle Main Menu Toggle Search

Open Access padlockePrints

Verification of bounded Petri nets using integer programming

Lookup NU author(s): Dr Victor Khomenko, Professor Maciej Koutny

Downloads


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. In [19], 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. To solve other verification problems, such as mutual exclusion or marking reachability and coverability, we adopt Contejean and 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. Another contribution of this paper is a method of re-formulating some problems specified in terms of Petri nets as problems defined for their unfoldings. Using this method, we obtain a memory efficient translation of a deadlock detection problem for a safe Petri net into an LP problem. We also propose an on-the-fly deadlock detection method. Experimental results demonstrate that the resulting algorithms can achieve significant speedups. © Springer Science+Business Media, LLC 2007.


Publication metadata

Author(s): Khomenko V, Koutny M

Publication type: Article

Publication status: Published

Journal: Formal Methods in System Design

Year: 2007

Volume: 30

Issue: 2

Pages: 143-176

ISSN (print): 0925-9856

ISSN (electronic): 1572-8102

Publisher: Springer

URL: http://dx.doi.org/10.1007/s10703-006-0022-1

DOI: 10.1007/s10703-006-0022-1


Altmetrics

Altmetrics provided by Altmetric


Actions

Find at Newcastle University icon    Link to this publication


Share