Skip to Main content Skip to Navigation
Journal articles

A lower bound for the coverability problem in acyclic pushdown VAS

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.
Document type :
Journal articles
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03447041
Contributor : Jérôme Leroux Connect in order to contact the contributor
Submitted on : Monday, November 29, 2021 - 9:49:10 AM
Last modification on : Tuesday, January 4, 2022 - 6:16:56 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Matthias Englert, Piotr Hofman, Sławomir Lasota, Ranko Lazić, Jérôme Leroux, et al.. A lower bound for the coverability problem in acyclic pushdown VAS. Information Processing Letters, Elsevier, 2021, 167, pp.106079. ⟨10.1016/j.ipl.2020.106079⟩. ⟨hal-03447041⟩

Share

Metrics

Les métriques sont temporairement indisponibles