User: Guest  Login
Title:

Reachability in Live and Safe Free-Choice Petri Nets is NP-complete

Document type:
Technical Report
Author(s):
Javier Esparza
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.
Keywords:
Free-Choice Petri nets; Reachability; NP-completeness
Year:
1996
Year / month:
1996-05-01 00:00:00
Pages:
13
 BibTeX