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

Stefan Goller, Christoph Haase, Ranko Lazic, Patrick Totzke

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationThe 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science (EATCS)
Place of PublicationRome, Italy
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages105:1-105:13
Number of pages13
ISBN (Electronic)978-3-95977-013-2
DOIs
Publication statusPublished - 15 Jul 2016
Event43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science - Sapienza University of Rome, Rome, Italy
Duration: 12 Jul 201615 Jul 2016
http://www.easyconferences.eu/icalp2016/
http://www.easyconferences.eu/icalp2016/index.html

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume55
ISSN (Electronic)1868-8969

Conference

Conference43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), the main European conference in Theoretical Computer Science and annual meeting of the European Association for Theoretical Computer Science
Abbreviated titleICALP 2016
Country/TerritoryItaly
CityRome
Period12/07/1615/07/16
Internet address

Fingerprint

Dive into the research topics of 'A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One'. Together they form a unique fingerprint.
  • Energy Efficient Control

    Mayr, R.

    EPSRC

    1/09/1531/08/19

    Project: Research

Cite this