In: Journal of Theoretical Computer Science, Vol. 64, No. 3, pages 305-329. 1989.
Abstract: The authors examine the complexity of the fair nontermination problem for conflict-free Petri nets under several definitions of fairness. For each definition of fairness, they are able to show the problem to be complete for either NP, PTIME, or NLOGSPACE. They then address the question of whether these results extend to the more general model checking problem with respect to temporal logic. It turns out that unless the logic is severely restricted, model checking is undecidable for conflict-free Petri nets.
Back to the Petri Nets Bibliography