๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Reachability in live and safe free-choice Petri nets is NP-complete

โœ Scribed by Javier Esparza

Book ID
104326368
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
887 KB
Volume
198
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

On commoner's liveness theorem and super
On commoner's liveness theorem and supervisory policies that enforce liveness in free-choice Petri nets
โœ Ramavarapu S. Sreenivas ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 613 KB

A Petri net (PN) (Pe::erson, 1981;Reisig, 1985) is said to be live if it is possible to fire any transition from every reachable marking, although not: necessarily immediately. A free-choice Petri net (FCPN) is a PN, where every arc from a place to a transition is either t~e unique output arc from t