Complexity Results for 1-safe Nets
Open Access
- 1 September 1993
- journal article
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (455)
- https://doi.org/10.7146/dpb.v22i455.6773
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. This paper is to be presented at FST & TCS, Foundations of Software Technology & Theoretical Computer Science, to be held 15-17 December 1993, in Bombay, India.A version of the paper with most proofs omitted is to appear in the proceedings.Keywords
This publication has 0 references indexed in Scilit: