For the most recent entries see the Petri Nets Newsletter.

Complexity Results for 1-Safe Nets.

Cheng, A.; Esparza, J.; Palsberg, J.

In: Computer Science Department of Aarhus University, DAIMI PB-455, Sept. 93. 1993.

Also in: Theoretical Computer Science, Vol. 147, No. 1-2, pages 117-136. 1995.

Abstract: We study the complexity of several standard problems for 1-safe Petri nets and some of its subclasses. We prove that reachability, liveness, and deadlock are all PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-complete for free-choice nets and for 1-safe free-choice nets. Finally, we prove that for arbitrary Petri nets, deadlock is equivalent to reachability and liveness.

Keywords: complexity results, free-choice Petri nets, reachability analysis.

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

Back to the Petri Nets Bibliography