Complexity Results for 1-safe Nets
DOI:
https://doi.org/10.7146/dpb.v22i455.6773Resumé
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.
Downloads
Publiceret
Citation/Eksport
Nummer
Sektion
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.