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

DOI10.4230/LIPICS.ICALP.2017.119zbMATH Open1442.68136OpenAlexW2612695319MaRDI QIDQ5111451FDOQ5111451

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

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

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)

Cited In (7)

• Constructive decision via redundancy-free proof-search
• The reachability problem for branching vector addition systems requires doubly-exponential space
• 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
• Title not available (Why is that?)

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)