Lower bounds for the reachability problem in fixed dimensional VASSes

DOI10.1145/3531130.3533357MaRDI QIDQ6649473zbMATH OpenFDO

Authors Wojciech Czerwiński, Lukasz Orlikowski

Publication date 6 December 2024

Full work available at URL https://doi.org/10.1145/3531130.3533357

zbMATH Keywords

lower boundsPetri netsreachability problemvector addition systems

Mathematics Subject Classification ID

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

Cites work

• Complexity hierarchies beyond elementary
• CONCUR 2004 - Concurrency Theory
• Counter machines and counter languages
• Directed reachability for infinite-state systems
• scientific article; zbMATH DE number 7559504 (Why is no real title available?)
• Ideal decompositions for vector addition systems (invited talk)
• Reachability in Succinct and Parametric One-Counter Automata
• Reachability in two-dimensional unary vector addition systems with states is NL-complete
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• The reachability problem for Petri nets is not elementary
• The Reachability Problem for Petri Nets Is Not Elementary
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States

Cited in

(5)

• Coverability in VASS revisited: improving Rackoff's bounds to obtain conditional optimality
• New lower bounds for reachability in vector addition systems
• Monus semantics in vector addition systems with states
• Challenges of the reachability problem in infinite-state systems (invited paper)
• Reachability in symmetric VASS

This page was built for publication: Lower bounds for the reachability problem in fixed dimensional VASSes

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