The Library
A lower bound for the coverability problem in acyclic pushdown VAS
Tools
Tools
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
|
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 > 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 | ||||||||||||
| 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
