UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One

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. Green open access

[thumbnail of LIPIcs-ICALP-2016-105.pdf]
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
Downloads since deposit
Loading...
15Downloads
Download activity - last month
Loading...
Download activity - last 12 months
Loading...
Downloads by country - last 12 months
Loading...

Archive Staff Only

View Item View Item