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

DOI10.1016/S0304-3975(97)00235-1zbMath0902.68136OpenAlexW2018409411MaRDI QIDQ1129263

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)

Related Items

Static analysis and stochastic search for reachability problem ⋮ Free-choice Nets with Home Clusters are Lucent ⋮ Soundness of workflow nets: classification, decidability, and analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reachability in cyclic extended free-choice systems
• A polynomial-time algorithm to decide liveness of bounded free choice nets
• Free Choice Petri Nets
• Handles and reachability analysis of free choice nets