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

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

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

(12)

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

Describes a project that uses

Uses Software

• caesar.bdd
• CAESAR
• NUPN_INFO

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)