← All problems
Unverified
Fine Grained Complexity for VAS Boundedness
A (-dimensional) Vector Addition System is a set of vectors and induces a single-step transition relation by for some . The transitive closure of , , is called the reachability relation and for some vector , we call the reachability set of . The boundedness problem for VAS asks if, given a vector , the set is finite. It has been long known that the boundedness problem for VAS is EXPSPACE-complete. A more careful analysis reveals an upper bound of . A similar upper bound for VAS coverability was recently tightened to . Can we tighten the upper bound for boundedness too?
