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

DOI10.1016/S0304-3975(97)00235-1zbMATH Open0902.68136OpenAlexW2018409411MaRDI QIDQ1129263FDOQ1129263

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

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

zbMATH Keywords

reachabilityPetri nets

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Free Choice Petri Nets
• Title not available (Why is that?)
• A polynomial-time algorithm to decide liveness of bounded free choice nets
• Reachability in cyclic extended free-choice systems
• Handles and reachability analysis of free choice nets

Cited In (13)

• On complexity of reachability of transition restricted 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
• Title not available (Why is that?)
• On Yen’s Path Logic for Petri Nets
• Static analysis and stochastic search for reachability problem
• Soundness of workflow nets: classification, decidability, and analysis
• Structure of the submarking-reachability problem and network programming
• Analyzing the reachability problem in choice networks
• The complexity of problems involving structurally bounded and conservative Petri nets
• New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
• Free-choice Nets with Home Clusters are Lucent
• Title not available (Why is that?)

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)