For the most recent entries see the Petri Nets Newsletter.

Problems Concerning Fairness and Temporal Logic for Conflict-Free Petri Nets.

Howell, R.R.; Rosier, L.E.

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.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography