Solvability for The Maximum Legal Firing Sequence Problem of Inhibitor-Arc Petri nets Unweighted/Weighted Conflict-Free Petri nets

摘要

The subject of this paper is the maximum legal firing sequence problem (MAX-INLFS) for inhibitor-arc Petri nets IN. Let MAX-LFS denote MAX-INLFS in which IN has no inhibitor arcs. The underlying Petri net N of IN is a Petri net with all inhibitor arcs removed from IN. It is well-known that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines, and MAX-INLFS has wide applications to fundamental problems of Petri net such as the marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem, and so on. This paper proves that MAX-INLFS can be solved in 0(PX) time when the underlying Petri net N of IN is a weighted marked graph and IN has only one place (called a rivet) to which at least one inhibitor-arc is incident, and shows that MAX-INLFS is NP-hard when the underlying Petri net N of IN is a weighted conflict-free Petri net and IN has only one rivet.