@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",
}