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

Marvin Künnemann, Filip Mazowiecki, Lia Schütze +2

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 encodi…