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

Englert, Matthias, Lazic, Ranko S and Totzke, Patrick ORCID: 0000-0001-5274-8190 (2016) Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete. In: 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016-7-5 - 2016-7-8, ’16, New York, NY, USA, July 5-8, 2016.

Access the full-text of this item by clicking on the Open Access link.

Official URL: https://doi.org/10.1145/2933575

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 or Workshop Item (Unspecified)
Additional Information:	timestamp: Fri, 21 Dec 2018 14:34:10 +0100 biburl: https://dblp.org/rec/bib/conf/lics/2016 bibsource: dblp computer science bibliography, https://dblp.org
Uncontrolled Keywords:	cs.LO, cs.LO, F.1.1
Depositing User:	Symplectic Admin
Date Deposited:	21 Jan 2019 15:25
Last Modified:	11 Nov 2023 01:27
DOI:	10.1145/2933575
Open Access URL:	http://wrap.warwick.ac.uk/78941/
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3031040