Complexity results for 1-safe nets

Allan Cheng; Javier Esparza; Jens Palsberg

doi:10.1016/0304-3975(94)00231-7

Complexity results for 1-safe nets

Allan Cheng, Javier Esparza, Jens Palsberg

Informatics 7 - Chair of Theoretical Computer Science

Aarhus University

Research output: Contribution to journal › Article › peer-review

97 Scopus citations

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.

Original language	English
Pages (from-to)	117-136
Number of pages	20
Journal	Theoretical Computer Science
Volume	147
Issue number	1-2
DOIs	https://doi.org/10.1016/0304-3975(94)00231-7
State	Published - 7 Aug 1995

Access to Document

10.1016/0304-3975(94)00231-7

Cite this

@article{f88888604673470d8084f16eb6ba3d3c,

title = "Complexity results for 1-safe nets",

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.",

author = "Allan Cheng and Javier Esparza and Jens Palsberg",

year = "1995",

month = aug,

day = "7",

doi = "10.1016/0304-3975(94)00231-7",

language = "English",

volume = "147",

pages = "117--136",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Complexity results for 1-safe nets

AU - Cheng, Allan

AU - Esparza, Javier

AU - Palsberg, Jens

PY - 1995/8/7

Y1 - 1995/8/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029638650&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(94)00231-7

DO - 10.1016/0304-3975(94)00231-7

M3 - Article

AN - SCOPUS:0029638650

SN - 0304-3975

VL - 147

SP - 117

EP - 136

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Complexity results for 1-safe nets

Abstract

Access to Document

Other files and links

Fingerprint

Cite this