The Complexity of Coverability in Vector Addition Systems with States

A d-dimensional vector addition system with states can be seen as a directed graph whose edges are labelled with d-dimensional integer vectors. The coverability problem asks from an initial node whether there exists a path to a target node such that sum of the vectors observed along the path remains non-negative on all k components throughout. The problem and its complexity has been studied in great detail, as already since the late seventies, coverability is known to require exponential space but can also be decided using exponential space. In this presentation I will define the problem, overview its history, and describe the state-of-the-art.

FoCS Theory Day 2023

Henry Sinclair-Banks, 08/06/23, University of Warwick (UK).