In: Rozenberg, G.: Lecture Notes in Computer Science, Vol. 340: Advances in Petri Nets 1988, pages 200-226. Springer-Verlag, 1988.
Abstract: The complexity of the fair nontermination problem for conflict-free Petri nets is examined. For several definitions for fairness it is shown that the problem is complete for either NP, PTIME or NLOGSPACE. Then the question is addressed of whether these results extend to the more general model checking problem with respect to the temporal logic for Petri nets introduced by Suzuki. It turns out that unless the logic is severely restricted, model checking is undecidable for conflict-free Petri nets.