2026-08-17T17:41:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18183 2024-03-06T11:01:15Z ddc:004 open_access

Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality Künnemann, Marvin Mazowiecki, Filip Schütze, Lia Sinclair-Banks, Henry Węgrzycki, Karol Vector Addition System Coverability Reachability Fine-Grained Complexity Exponential Time Hypothesis k-Cycle Hypothesis Hyperclique Hypothesis Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most n^{2^𝒪(d log d)}, where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d-dimensional unary VASS that are only witnessed by runs of length at least n^{2^Ω(d)}. Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated log(d) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic n^{2^𝒪(d)}-time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic n^{2^o(d)}-time algorithm, conditioned upon the Exponential Time Hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in 𝒪(n^{d+1})-time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that n^{2-o(1)}-time is required under the k-cycle hypothesis. In general fixed dimension d, we show that n^{d-2-o(1)}-time is required under the 3-uniform hyperclique hypothesis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marvin Künnemann and Filip Mazowiecki and Lia Schütze and Henry Sinclair-Banks and Karol Węgrzycki 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.131 urn:nbn:de:0030-drops-181834 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.131 eng https://creativecommons.org/licenses/by/4.0/legalcode