Petri nets with simple circuits
Journal
IEICE Transactions on Information and Systems
Journal Volume
E88-D
Journal Issue
9
Pages
2113-2125
Date Issued
2005
Author(s)
Abstract
We study the complexity of the reachability problem for a new subclass of Petri nets called simple-circuit Petri nets, which properly contains several well known subclasses such as conflict-free, BPP, normal Petri nets and more. A new decomposition approach is applied to developing an integer linear programming formulation for characterizing the reachability sets of such Petri nets. Consequently, the reachability problem is shown to be NP-complete. The model checking problem for some temporal logics is also investigated for simple-circuit Petri nets.
Type
journal article