Göller, S;
Haase, C;
Lazic, R;
Totzke, P;
(2016)
A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One.
In: Chatzigiannakis, I and Mitzenmacher, M and Rabani, Y and Sangiorgi, D, (eds.)
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
(pp. 105:1-105:13).
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany.
Preview |
Text
LIPIcs-ICALP-2016-105.pdf - Published Version Download (638kB) | Preview |
Abstract
Branching VASS (BVASS) generalise vector addition systems with states by allowing for special branching transitions that can non-deterministically distribute a counter value between two control states. A run of a BVASS consequently becomes a tree, and reachability is to decide whether a given configuration is the root of a reachability tree. This paper shows P-completeness of reachability in BVASS in dimension one, the first decidability result for reachability in a subclass of BVASS known so far. Moreover, we show that coverability and boundedness in BVASS in dimension one are P-complete as well.
Type: | Proceedings paper |
---|---|
Title: | A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One |
Event: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
ISBN-13: | 978-3-95977-013-2 |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.4230/LIPIcs.ICALP.2016.105 |
Publisher version: | https://doi.org/10.4230/LIPIcs.ICALP.2016.105 |
Language: | English |
Additional information: | Copyright © Stefan Göller, Christoph Haase, Ranko Lazić, and Patrick Totzke; licensed under Creative Commons License CC-BY (http://creativecommons.org/licenses/by/3.0/). |
Keywords: | branching vector addition systems, reachability, coverability, boundedness |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/10088925 |
Archive Staff Only
View Item |