@article{ENGLERT2020106079,
    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.},
    Author = {Englert, Matthias and Hofman, Piotr and Lasota, S{{\l}}awomir and Lazi{\'c}, Ranko and Leroux, J{\'e}r{\^o}me and Straszy{\'n}ski, Juliusz},
    ISSN = {0020-0190},
    Journal = {Information Processing Letters},
    Keywords = {Theory of computation, Context-free grammars, Pushdown vector addition systems, One-counter machines, Coverability problem},
    Pages = {106079},
    Title = {A lower bound for the coverability problem in acyclic pushdown VAS},
    URL = {http://www.sciencedirect.com/science/article/pii/S0020019020301666},
    Year = {2020},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0020019020301666},
    bdsk-url-2 = {https://doi.org/10.1016/j.ipl.2020.106079},
    date-added = {2020-12-27 18:43:48 +0100},
    date-modified = {2020-12-27 18:43:48 +0100},
    doi = {10.1016/j.ipl.2020.106079}
}

@article{ENGLERT2020106079, 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.}, Author = {Englert, Matthias and Hofman, Piotr and Lasota, S{{\l}}awomir and Lazi{\'c}, Ranko and Leroux, J{\'e}r{\^o}me and Straszy{\'n}ski, Juliusz}, ISSN = {0020-0190}, Journal = {Information Processing Letters}, Keywords = {Theory of computation, Context-free grammars, Pushdown vector addition systems, One-counter machines, Coverability problem}, Pages = {106079}, Title = {A lower bound for the coverability problem in acyclic pushdown VAS}, URL = {http://www.sciencedirect.com/science/article/pii/S0020019020301666}, Year = {2020}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0020019020301666}, bdsk-url-2 = {https://doi.org/10.1016/j.ipl.2020.106079}, date-added = {2020-12-27 18:43:48 +0100}, date-modified = {2020-12-27 18:43:48 +0100}, doi = {10.1016/j.ipl.2020.106079} }