The Library
A polynomial-time algorithm for reachability in branching VASS in dimension one
Tools
Tools
Tools
Goller, Stefan, Haase, Christoph, Lazic, Ranko and Totzke, Patrick (2016) A polynomial-time algorithm for reachability in branching VASS in dimension one. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Rome, Italy, 12-15 Jul 2016. Published in: Leibniz International Proceedings in Informatics (LIPIcs) ISBN 9783959770132. doi:10.4230/LIPIcs.ICALP.2016.105 ISSN 1868-8969.
|
PDF
WRAP_0070379-cs-170516-icalp.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (1300Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.105
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.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Time -- Mathematical models -- Research, Polynomials, Algorithms | ||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||
| ISBN: | 9783959770132 | ||||
| ISSN: | 1868-8969 | ||||
| Official Date: | 15 April 2016 | ||||
| Dates: |
|
||||
| DOI: | 10.4230/LIPIcs.ICALP.2016.105 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Date of first compliant deposit: | 19 May 2016 | ||||
| Date of first compliant Open Access: | 19 May 2016 | ||||
| Funder: | Labex Digicosme, Université Paris-Saclay (UPS), Engineering and Physical Sciences Research Council (EPSRC) | ||||
| Grant number: | VERICONISS (UPS), EP/M011801/1 and EP/M027651/1 (EPSRC) | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Rome, Italy | ||||
| Date(s) of Event: | 12-15 Jul 2016 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
