Reachability in live and safe free-choice Petri nets is NP-complete

Javier Esparza

doi:10.1016/S0304-3975(97)00235-1

Reachability in live and safe free-choice Petri nets is NP-complete

Javier Esparza

Informatics 7 - Chair of Theoretical Computer Science

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

35 Scopus citations

Abstract

The complexity of the reachability problem for live and safe free-choice Petri nets has been open for several years. Several partial results seemed to indicate that the problem is polynomial. We show that this is unlikely: the problem is NP-complete.

Original language	English
Pages (from-to)	211-224
Number of pages	14
Journal	Theoretical Computer Science
Volume	198
Issue number	1-2
DOIs	https://doi.org/10.1016/S0304-3975(97)00235-1
State	Published - 30 May 1998

Access to Document

10.1016/S0304-3975(97)00235-1

Cite this

@article{53e91def3168404a84de1c31455b2ba5,

title = "Reachability in live and safe free-choice Petri nets is NP-complete",

abstract = "The complexity of the reachability problem for live and safe free-choice Petri nets has been open for several years. Several partial results seemed to indicate that the problem is polynomial. We show that this is unlikely: the problem is NP-complete.",

author = "Javier Esparza",

note = "Funding Information: I have discussed this problem with J\&g Desel many times, and I thank him very specially for sharing his insights with me. Many thanks also to Andrei Kovalyov, who renewedm y interesti n the problem during a recent visit to Munich funded by a DAAD Grant, and to Eike Best for very helpful discussions. Finally, it is a pleasure to thank Peter Niebert and an anonymous referee for their valuable comments.",

year = "1998",

month = may,

day = "30",

doi = "10.1016/S0304-3975(97)00235-1",

language = "English",

volume = "198",

pages = "211--224",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-2",

}

TY - JOUR

T1 - Reachability in live and safe free-choice Petri nets is NP-complete

AU - Esparza, Javier

N1 - Funding Information: I have discussed this problem with J&g Desel many times, and I thank him very specially for sharing his insights with me. Many thanks also to Andrei Kovalyov, who renewedm y interesti n the problem during a recent visit to Munich funded by a DAAD Grant, and to Eike Best for very helpful discussions. Finally, it is a pleasure to thank Peter Niebert and an anonymous referee for their valuable comments.

PY - 1998/5/30

Y1 - 1998/5/30

N2 - The complexity of the reachability problem for live and safe free-choice Petri nets has been open for several years. Several partial results seemed to indicate that the problem is polynomial. We show that this is unlikely: the problem is NP-complete.

AB - The complexity of the reachability problem for live and safe free-choice Petri nets has been open for several years. Several partial results seemed to indicate that the problem is polynomial. We show that this is unlikely: the problem is NP-complete.

UR - https://www.scopus.com/pages/publications/0346244056

U2 - 10.1016/S0304-3975(97)00235-1

DO - 10.1016/S0304-3975(97)00235-1

M3 - Article

AN - SCOPUS:0346244056

SN - 0304-3975

VL - 198

SP - 211

EP - 224

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Reachability in live and safe free-choice Petri nets is NP-complete

Abstract

Access to Document

Other files and links

Fingerprint

Cite this