zbMATH — the first resource for mathematics

Compositional reachability in Petri nets. (English) Zbl 1448.68351
Ouaknine, Joël (ed.) et al., Reachability problems. 8th international workshop, RP 2014, Oxford, UK, September 22–24, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8762, 230-243 (2014).
Summary: We introduce a divide-and-conquer algorithm for a modified version of the reachability/coverability problem in 1-bounded Petri nets that relies on the compositional algebra of nets with boundaries: we consider the algebraic decomposition of the net of interest as part of the input. We formally prove the correctness of the technique and contrast the performance of our implementation with state-of-the-art tools that exploit partial order reduction techniques on the global net.
For the entire collection see [Zbl 1317.68013].

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