Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One

DOI10.4230/LIPIcs.ICALP.2017.119zbMath1442.68136OpenAlexW2612695319MaRDI QIDQ5111451

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

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

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

Related Items (3)

Unnamed Item ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ Constructive decision via redundancy-free proof-search

This page was built for publication: Polynomial-Space Completeness of Reachability for Succinct Branching VASS in Dimension One