The Library
Reachability in two-dimensional unary vector addition systems with states is NL-complete
Tools
Englert, Matthias, Lazic, Ranko and Totzke, Patrick (2016) Reachability in two-dimensional unary vector addition systems with states is NL-complete. In: Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), New York City, USA, 5–8 Jul 2016. Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
|
PDF
WRAP_0771998-cs-060516-2vass.pdf - Accepted Version - Requires a PDF viewer. Download (745Kb) | Preview |
Official URL: http://lics.rwth-aachen.de/lics16/accepted.html
Abstract
Blondin et al. showed at LICS 2015 that two-dimensional vector addition systems with states have reachability witnesses of length exponential in the number of states and polynomial in the norm of vectors. The resulting guess-and-verify algorithm is optimal (PSPACE), but only if the input vectors are given in binary. We answer positively the main question left open by their work, namely establish that reachability witnesses of pseudo-polynomial length always exist. Hence, when the input vectors are given in unary, the improved guess-and-verify algorithm requires only logarithmic space.
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): | Exponential functions, Polynomials, Logarithmic functions, Algorithms | ||||
Journal or Publication Title: | Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||
Official Date: | 4 April 2016 | ||||
Dates: |
|
||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 9 May 2016 | ||||
Date of first compliant Open Access: | 9 June 2016 | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||
Grant number: | EP/M011801/1 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) | ||||
Type of Event: | Other | ||||
Location of Event: | New York City, USA | ||||
Date(s) of Event: | 5–8 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