The Library
The reachability problem for branching vector addition systems requires doubly-exponential space
Tools
Lazic, Ranko (2010) The reachability problem for branching vector addition systems requires doubly-exponential space. Information Processing Letters, Vol.110 (No.17). pp. 740-745. doi:10.1016/j.ipl.2010.06.008 ISSN 0020-0190.
PDF
rechrank.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (158Kb) |
Official URL: http://dx.doi.org/10.1016/j.ipl.2010.06.008
Abstract
Branching vector addition systems are an extension of vector addition systems where new reachable vectors may be obtained by summing two reachable vectors and adding an integral vector from a fixed finite set. The reachability problem for them is shown hard for doubly-exponential space. For an alternative extension of vector addition systems, where reachable vectors may be combined by subtraction, most decision problems of interest are shown undecidable. (C) 2010 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics 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): | Computer programs -- Correctness, System analysis, Graph theory | ||||
Journal or Publication Title: | Information Processing Letters | ||||
Publisher: | Elsevier Science BV | ||||
ISSN: | 0020-0190 | ||||
Official Date: | 15 August 2010 | ||||
Dates: |
|
||||
Volume: | Vol.110 | ||||
Number: | No.17 | ||||
Number of Pages: | 6 | ||||
Page Range: | pp. 740-745 | ||||
DOI: | 10.1016/j.ipl.2010.06.008 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 3 December 2015 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |