Toggle Main Menu Toggle Search

Open Access padlockePrints

An Efficient Algorithm for Unfolding Petri Nets

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

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 view of recent very efficient model checking algorithms, employing unfoldings ([10,11]), the problem of efficiently building them becomes of great interest. [6-8] address this issue, considerably improving the original McMillan's technique, but the unfolding algorithms proposed there are still relatively slow. In this paper, we put forward a method of computing possible extensions, which was the slowest part of the unfolding algorithm. Essentially, we show how to find new transition instances to be inserted in the unfolding, not trying all the transition one-by-one, but all at once, merging common parts of the work. Moreover, we propose some ways of reducing the number of candidate transitions to be inserted, and provide some additional heuristics, helping to speed up the algorithm. Experimental results demonstrate that the resulting algorithms can achieve significant speedups if the transitions of the Petri net being unfolded have large presets.


Publication metadata

Author(s): Koutny M, Khomenko V

Publication type: Report

Publication status: Published

Series Title: Department of Computing Science Technical Report Series

Year: 2001

Pages: 20

Report Number: 726

Institution: Department of Computing Science, University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

URL: http://www.cs.ncl.ac.uk/publications/trs/papers/726.pdf


Share