Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete

Matthias Englert, Ranko Lazic, Patrick Totzke

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

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationLICS '16 Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
Place of PublicationNew York, USA
PublisherACM
Pages477-484
Number of pages8
ISBN (Electronic)978-1-4503-4391-6
DOIs
Publication statusPublished - 5 Jul 2016
Event31st Annual ACM/IEEE Symposium on Logic in Computer Science - New York City, United States
Duration: 5 Jul 20168 Jul 2016
http://lics.siglog.org/lics16/

Conference

Conference31st Annual ACM/IEEE Symposium on Logic in Computer Science
Abbreviated titleLICS 2016
Country/TerritoryUnited States
CityNew York City
Period5/07/168/07/16
Internet address

Fingerprint

Dive into the research topics of 'Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete'. Together they form a unique fingerprint.

Cite this