Coverability for VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality

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^{\mathcal{O}(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^{\mathcal{O}(d)}} \)-time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic \(n^{2^{\mathcal{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 \( \mathcal{O}(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-\mathcal{o}(1)}\)-time is required under the k-cycle hypothesis. In general fixed dimension \(d\), we show that \(n^{d-2-\mathcal{o}(1)}\)-time is required under the 3-uniform hyperclique hypothesis.