The Library
Polynomial-space completeness of reachability for succinct branching VASS in dimension one
Tools
Figueira, Diego, Lazic, Ranko, Leroux, Jerome, Mazowiecki, Filip and Sutre, Grégoire (2017) Polynomial-space completeness of reachability for succinct branching VASS in dimension one. In: The 44th International Colloquium on Automata, Languages, and Programming (ICALP), Warsaw, Poland, 10-14 Jul 2017. Published in: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 80 119 : 1-119: 14. ISBN 9783959770415. doi:10.4230/LIPIcs.ICALP.2017.119 ISSN 1868-8969.
|
PDF
WRAP-polynomial-space-completeness-reachability-VoR_Lazic-2017.pdf.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (784Kb) | Preview |
|
|
PDF
WRAP-polynomial-space-completeness-reachability-Lazic-2017.pdf - Publisher's Proof Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1219Kb) | Preview |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.119
Abstract
Whether the reachability problem for branching vector addition systems, or equivalently the provability problem for multiplicative exponential linear logic, is decidable has been a long-standing open question. The one-dimensional case is a generalisation of the extensively studied one-counter nets, and it was recently established polynomial-time complete provided counter updates are given in unary. Our main contribution is to determine the complexity when the encoding is binary: polynomial-space complete.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Petri nets, Computer logic, Polynomials | ||||||
Journal or Publication Title: | 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) | ||||||
ISBN: | 9783959770415 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 14 April 2017 | ||||||
Dates: |
|
||||||
Volume: | 80 | ||||||
Page Range: | 119 : 1-119: 14 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2017.119 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 28 April 2017 | ||||||
Date of first compliant Open Access: | 3 May 2017 | ||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), Royal Society (Great Britain) | ||||||
Grant number: | EP/M011801/1 (EPSRC), E150122 (Royal Society (Great Britain)) | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | The 44th International Colloquium on Automata, Languages, and Programming (ICALP) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Warsaw, Poland | ||||||
Date(s) of Event: | 10-14 Jul 2017 | ||||||
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