Vector addition systems reachability problem (a simpler solution)

DOI10.29007/BNX2MaRDI QIDQ6874948zbMATH OpenFDO

Authors Jérôme Leroux

Publication date 14 January 2026

Full work available at URL https://doi.org/10.29007/BNX2

zbMATH Keywords

Petri netPresburger arithmeticreachability problemVAS

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cites work

• A primitive recursive algorithm for the general Petri net reachability problem
• A structure to decide reachability in Petri nets
• Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm
• Decidability of a temporal logic problem for Petri nets
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• On the reachability problem for 5-dimensional vector addition systems
• Semigroups, Presburger formulas, and languages
• The Complexity of the Finite Containment Problem for Petri Nets
• Vector addition system reachability problem, a short self-contained proof

Cited in

(7)

• Flattability of priority vector addition systems
• The semilinear home-space problem is Ackermann-complete for Petri nets
• Geometry of reachability sets of vector addition systems
• Verifying unboundedness via amalgamation
• On the home-space problem for Petri nets and its Ackermannian complexity
• Improved lower bounds for reachability in vector addition systems
• Bridging the gap between plain VASS and branching VASS

This page was built for publication: Vector addition systems reachability problem (a simpler solution)

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