Reachability in live and safe free-choic
โ
Javier Esparza
๐
Article
๐
1998
๐
Elsevier Science
๐
English
โ 887 KB
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.