Polynomial-space completeness of reachability for succinct branching VASS in dimension one

DOI10.4230/LIPICS.ICALP.2017.119MaRDI QIDQ5111451zbMATH OpenOpenAlexFDO

Authors Diego Figueira, Ranko Lazić, Jérôme Leroux, Filip Mazowiecki, Grégoire Sutre

Publication date 27 May 2020

Full work available at URL https://hal.archives-ouvertes.fr/hal-01688742

zbMATH Keywords

reachability problembranching vector addition systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decidability of theories and sets of sentences (03B25) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• A polynomial-time algorithm for reachability in branching VASS in dimension one
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• The reachability problem for branching vector addition systems requires doubly-exponential space

Cited in

(7)

• The reachability problem for branching vector addition systems requires doubly-exponential space
• Constructive decision via redundancy-free proof-search
• Reachability problem for polynomial iteration is PSPACE-complete
• Deciding Polynomial Termination Complexity for VASS Programs
• Strategic reasoning with a bounded number of resources: the quest for tractability
• A polynomial-time algorithm for reachability in branching VASS in dimension one
• scientific article; zbMATH DE number 7649936 (Why is no real title available?)

This page was built for publication: Polynomial-space completeness of reachability for succinct branching VASS in dimension one

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