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.