Reachability in Fixed VASS: Expressiveness and Lower Bounds

Andrei Draghici, Christoph Haase, Andrew Ryzhikov

The recent years have seen remarkable progress in establishing the complexity of the reachability problem for vector addition systems with states (VASS), equivalently known as Petr…