← All problems
Unverified
Complexity of fixed VAS reachability
A vector addition system is a finite set of vectors with . Given two positions , a run of from to is a sequence of positions where each position is obtained by adding an element of to the previous one: for every . Is the following statement correct: Conjecture: For every vector addition system , there exists a constant such that for every pair of positions and , if there exists at least one run of from to , one of these runs has a length smaller than .
