Efficient algorithms for three reachability problems in safe Petri nets

DOI10.1007/978-3-030-76983-3_17MaRDI QIDQ2117182zbMATH OpenOpenAlexFDO

Authors Pierre Bouvier, Hubert Garavel

Publication date 21 March 2022

Full work available at URL https://hal.inria.fr/hal-03286069/file/Bouvier-Garavel-21-a.pdf

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1354143
• Complexity results for 1-safe nets
• Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
• Unfolding based alorithms for the reachability problem
• On the Efficient Computation of the Minimal Coverability Set for Petri Nets

Cites work

• Automatic decomposition of Petri nets into automata networks -- a synthetic account
• Complexity results for 1-safe nets
• Free Choice Petri Nets
• Nested-unit Petri nets
• Nets, sequential components and concurrency relations
• State space reduction for process algebra specifications

Cited in

(14)

• Solving liveness problem for marked nets by exhaustive coverability trees
• Reachability in live and safe free-choice Petri nets is NP-complete
• Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems
• Unfolding based alorithms for the reachability problem
• Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
• Compositional reachability in Petri nets
• Efficient computerized Petri net approach for the enumeration of the sets of path identifiers for reliability analysis of broadcasting networks
• scientific article; zbMATH DE number 1354143 (Why is no real title available?)
• scientific article; zbMATH DE number 1822236 (Why is no real title available?)
• Stop-transitions of Petri nets
• Applications and Theory of Petri Nets 2004
• Avoid one's doom: finding cliff-edge configurations in Petri nets
• Complexity results for 1-safe nets
• Accelerating the computation of dead and concurrent places using reductions

Describes a project that uses

Uses Software

• caesar.bdd
• NUPN_INFO
• CAESAR

This page was built for publication: Efficient algorithms for three reachability problems in safe Petri nets

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