Complexity results for 1-safe-nets

DOI10.1007/3-540-57529-4_66MaRDI QIDQ4268457zbMATH OpenFDO

Authors Allan Cheng, Javier Esparza, Jens Palsberg

Publication date 31 October 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57529-4_66

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Complexity results for 1-safe nets
• Reachability in live and safe free-choice Petri nets is NP-complete
• Efficient algorithms for three reachability problems in safe Petri nets
• Petri nets with simple circuits
• Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems

Cited in

(32)

• The complexity of problems involving structurally bounded and conservative Petri nets
• Well-structuredness, safeness and soundness: a formal classification of BPMN collaborations
• Efficient algorithms for three reachability problems in safe Petri nets
• Complexity of the deadlock problem for Petri nets modeling resource allocation systems
• Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable
• Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
• Uniqueness of minimal 1-safe Petri net generating all the binary n-vectors as its marking vectors exactly once
• Petri nets with non-blocking arcs are difficult to analyze
• Completeness results for generalized communication-free Petri nets with arbitrary arc multiplicities
• Petri nets with simple circuits
• Parameterized Complexity Results for 1-safe Petri Nets
• Liveness of safe object nets
• Directed Unfolding of Petri Nets
• Decompositional Petri Net Reductions
• scientific article; zbMATH DE number 3934416 (Why is no real title available?)
• scientific article; zbMATH DE number 4024806 (Why is no real title available?)
• scientific article; zbMATH DE number 4033101 (Why is no real title available?)
• scientific article; zbMATH DE number 17543 (Why is no real title available?)
• scientific article; zbMATH DE number 176140 (Why is no real title available?)
• scientific article; zbMATH DE number 1337888 (Why is no real title available?)
• scientific article; zbMATH DE number 862267 (Why is no real title available?)
• Universal safety for timed Petri nets is PSPACE-complete
• scientific article; zbMATH DE number 7438162 (Why is no real title available?)
• Petri nets, traces, and local model checking
• Completeness results for generalized communication-free Petri nets with arbitrary edge multiplicities
• Deriving Complexity Results for Interaction Systems from 1-Safe Petri Nets
• Everything Is PSPACE-Complete in Interaction Systems
• Avoid one's doom: finding cliff-edge configurations in Petri nets
• HyperMonitor: a Python prototype for hyper predictive runtime verification
• The complexity of soundness in workflow nets
• Complexity results for 1-safe nets
• The parallel complexity of two problems on concurrency

This page was built for publication: Complexity results for 1-safe-nets

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