The Library
The reachability problem for two-dimensional vector addition systems with states
Tools
Blondin, Michael, Englert, Matthias, Finkel, Alain, Göller, Stefan , Haase, Christoph, Lazic, Ranko, McKenzie, Pierre and Totzke, Patrick (2021) The reachability problem for two-dimensional vector addition systems with states. Journal of the ACM, 68 (5). pp. 1-43. 34. doi:10.1145/3464794 ISSN 0004-5411.
|
PDF
WRAP-Reachability-problem-two-dimensional-vector-addition-systems-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1616Kb) | Preview |
Official URL: https://doi.org/10.1145/3464794
Abstract
We prove that the reachability problem for two-dimensional vector addition systems with states is NL-complete or PSPACE-complete, depending on whether the numbers in the input are encoded in unary or binary. As a key underlying technical result, we show that if a configuration is reachable then there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This in turn enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded.
Item Type: | Journal Article | |||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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): | Machine theory, Computational complexity, Petri nets , Vector analysis | |||||||||||||||||||||||||||
Journal or Publication Title: | Journal of the ACM | |||||||||||||||||||||||||||
Publisher: | Association for Computing Machinery, Inc. | |||||||||||||||||||||||||||
ISSN: | 0004-5411 | |||||||||||||||||||||||||||
Official Date: | October 2021 | |||||||||||||||||||||||||||
Dates: |
|
|||||||||||||||||||||||||||
Volume: | 68 | |||||||||||||||||||||||||||
Number: | 5 | |||||||||||||||||||||||||||
Page Range: | pp. 1-43 | |||||||||||||||||||||||||||
Article Number: | 34 | |||||||||||||||||||||||||||
DOI: | 10.1145/3464794 | |||||||||||||||||||||||||||
Status: | Peer Reviewed | |||||||||||||||||||||||||||
Publication Status: | Published | |||||||||||||||||||||||||||
Reuse Statement (publisher, data, author rights): | "© ACM, 2021. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, 68(5) Oct 2021 http://doi.acm.org/10.1145/3464794 | |||||||||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||||||||
Date of first compliant deposit: | 18 May 2021 | |||||||||||||||||||||||||||
Date of first compliant Open Access: | 19 May 2021 | |||||||||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||||||||
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