The reachability problem for branching vector addition systems requires doubly-exponential space
DOI10.1016/J.IPL.2010.06.008zbMATH Open1234.68139OpenAlexW2108820019MaRDI QIDQ407525FDOQ407525
Authors: Ranko Lazić 
Publication date: 27 March 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2010.06.008
Recommendations
- Polynomial-space completeness of reachability for succinct branching VASS in dimension one
- Vector Addition System Reversible Reachability Problem
- Vector addition system reversible reachability problem
- Reachability in two-dimensional vector addition systems with states is PSPACE-complete
- Polynomial vector addition systems with states
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Parallel program schemata
- Two-variable logic on data trees and XML reasoning
- The covering and boundedness problems for vector addition systems
- Title not available (Why is that?)
- A structure to decide reachability in Petri nets
- Title not available (Why is that?)
- An Algorithm for the General Petri Net Reachability Problem
- Title not available (Why is that?)
- The covering and boundedness problems for branching vector addition systems
- Karp-Miller trees for a branching extension of VASS
Cited In (4)
This page was built for publication: The reachability problem for branching vector addition systems requires doubly-exponential space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407525)
