Complexity Results for 1-safe Nets

Authors

  • Allan Cheng
  • Javier Esparza
  • Jens Palsberg

DOI:

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.

Author Biographies

Allan Cheng

Javier Esparza

Jens Palsberg

Downloads

Published

1993-09-01

How to Cite

Cheng, A., Esparza, J., & Palsberg, J. (1993). Complexity Results for 1-safe Nets. DAIMI Report Series, 22(455). https://doi.org/10.7146/dpb.v22i455.6773

Issue

No. 455 (1993): PB-455 Complexity Results for 1-safe Nets

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.