The Library
A lower bound for the coverability problem in acyclic pushdown VAS
Tools
Englert, Matthias, Hofman, Piotr, Lasota, Sławomir, Lazic, Ranko, Leroux, Jérôme and Straszyński, Juliusz (2021) A lower bound for the coverability problem in acyclic pushdown VAS. Information Processing Letters, 167 . 106079. doi:10.1016/j.ipl.2020.106079 ISSN 0020-0190.
|
PDF
WRAP-lower-bound-coverability-problem-acyclic-pushdown-VAS-Englert-2021.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (1302Kb) | Preview |
Official URL: https://doi.org/10.1016/j.ipl.2020.106079
Abstract
We investigate the coverability problem for a one-dimensional restriction of pushdown vector addition systems with states. We improve the lower complexity bound to PSpace, even in the acyclic case.
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): | Modeling languages (Computer science) | ||||||||||||
Journal or Publication Title: | Information Processing Letters | ||||||||||||
Publisher: | Elsevier Science BV | ||||||||||||
ISSN: | 0020-0190 | ||||||||||||
Official Date: | April 2021 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 167 | ||||||||||||
Article Number: | 106079 | ||||||||||||
DOI: | 10.1016/j.ipl.2020.106079 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
Date of first compliant deposit: | 5 January 2021 | ||||||||||||
Date of first compliant Open Access: | 18 December 2021 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year