Integer reachability in VASS with transfers: a refined complexity analysis

Tymoteusz Kucharek, Piotr Hofman

Integer reachability is NP-complete for vector addition systems with states (VASS), but becomes PSPACE-complete in the presence of transfer operations. We refine this complexity ga…