Login
- Dokumenttyp:
- Technical Report
- Autor(en):
- Javier Esparza
- Titel:
- 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.
- Stichworte:
- Free-Choice Petri nets; Reachability; NP-completeness
- Jahr:
- 1996
- Jahr / Monat:
- 1996-05-01 00:00:00
- Seiten/Umfang:
- 13
BibTeX