22.1 Complexity of fixed VAS reachability

A vector addition system is a finite set of vectors \(V = \{ v_1,v_2,\ldots,v_n \} \in \mathbb{Z}^d\) with \(d \in \mathbb{N}\). Given two positions \(s,t \in \mathbb{N}^d\), a run of \(V\) from \(s\) to \(t\) is a sequence \(s = c_0, c_1, c_2, \ldots, c_m = t\) of positions \(c_i \in \mathbb{N}^d\) where each position is obtained by adding an element of \(V\) to the previous one: \(c_{i} - c_{i-1} \in V\) for every \(1 \leq i \leq m\). Is the following statement correct:

Conjecture: For every vector addition system \(V\), there exists a constant \(C_V\) such that for every pair of positions \(s\) and \(t\), if there exists at least one run of \(V\) from \(s\) to \(t\), one of these runs has a length smaller than \(C_V \cdot \big(||s|| + ||t|| \big)\).