The reachability problem for branching vector addition systems requires doubly-exponential space

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. ISSN 0020-0190

Full text not available from this repository.

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 > 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
Date:15 August 2010
Volume:Vol.110
Number:No.17
Number of Pages:6
Page Range:pp. 740-745
Identification Number:doi:10.1016/j.ipl.2010.06.008
Status:Peer Reviewed
Publication Status:Published
Access rights to Published version:Restricted or Subscription Access

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Repository Staff Only: item control page

WRAP: Warwick Research Archive Portal is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.