The reachability problem for branching vector addition systems requires doubly-exponential space

DOI10.1016/J.IPL.2010.06.008MaRDI QIDQ407525zbMATHOpenAlexFDO

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

zbMATH Keywords

theory of computationprogram correctness

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3885321 (Why is no real title available?)
• scientific article; zbMATH DE number 1302047 (Why is no real title available?)
• scientific article; zbMATH DE number 559221 (Why is no real title available?)
• A structure to decide reachability in Petri nets
• An Algorithm for the General Petri Net Reachability Problem
• Karp-Miller trees for a branching extension of VASS
• Parallel program schemata
• The covering and boundedness problems for branching vector addition systems
• The covering and boundedness problems for vector addition systems
• Two-variable logic on data trees and XML reasoning

Cited in

(4)

• A polynomial-time algorithm for reachability in branching VASS in dimension one
• Polynomial-space completeness of reachability for succinct branching VASS in dimension one
• Exponential space complexity for OBDD-based reachability analysis
• Expand, Enlarge, and Check for Branching Vector Addition Systems

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)