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

Titel:: Reachability in Live and Safe Free-Choice Petri Nets is NP-complete
Dokumenttyp:: Technical Report
Autor(en):: 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.
Stichworte:: Free-Choice Petri nets; Reachability; NP-completeness
Jahr:: 1996
Jahr / Monat:: 1996-05-01 00:00:00
Seiten/Umfang:: 13
BibTeX

Vorkommen: