2026-07-23T05:29:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14197 2024-03-06T10:53:43Z ddc:004 open_access

Improved Lower Bounds for Reachability in Vector Addition Systems Czerwiński, Wojciech Lasota, Sławomir Orlikowski, Łukasz Petri nets vector addition systems reachability problem We investigate computational complexity of the reachability problem for vector addition systems (or, equivalently, Petri nets), the central algorithmic problem in verification of concurrent systems. Concerning its complexity, after 40 years of stagnation, a non-elementary lower bound has been shown recently: the problem needs a tower of exponentials of time or space, where the height of tower is linear in the input size. We improve on this lower bound, by increasing the height of tower from linear to exponential. As a side-effect, we obtain better lower bounds for vector addition systems of fixed dimension. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Sławomir Lasota and Łukasz Orlikowski 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.128 urn:nbn:de:0030-drops-141973 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.128 eng https://creativecommons.org/licenses/by/4.0/legalcode