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

DOI10.1016/S0304-3975(97)00235-1MaRDI QIDQ1129263zbMATH OpenOpenAlexFDO

Authors Javier Esparza

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)00235-1

zbMATH Keywords

reachabilityPetri nets

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• scientific article; zbMATH DE number 4033101
• scientific article; zbMATH DE number 762060
• Approximating Petri net reachability along context-free traces
• The reachability problem for Petri nets is not elementary
• The Reachability Problem for Petri Nets Is Not Elementary
• Compositional reachability in Petri nets
• Efficient algorithms for three reachability problems in safe Petri nets
• Reduction and synthesis of live and bounded free choice Petri nets
• A note on the reachability set of Petri nets

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 47952 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial-time algorithm to decide liveness of bounded free choice nets
• Free Choice Petri Nets
• Handles and reachability analysis of free choice nets
• Reachability in cyclic extended free-choice systems

Cited in

(13)

• Free-choice Nets with Home Clusters are Lucent
• New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
• On Yen’s Path Logic for Petri Nets
• The complexity of some reachability problems for a system on a finite group
• On Computation Complexity of the Concurrently Enabled Transition Set Problem
• Static analysis and stochastic search for reachability problem
• The complexity of problems involving structurally bounded and conservative Petri nets
• Soundness of workflow nets: classification, decidability, and analysis
• scientific article; zbMATH DE number 4106272 (Why is no real title available?)
• On complexity of reachability of transition restricted Petri nets
• Structure of the submarking-reachability problem and network programming
• scientific article; zbMATH DE number 176520 (Why is no real title available?)
• Analyzing the reachability problem in choice networks

This page was built for publication: Reachability in live and safe free-choice Petri nets is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1129263)