In “The covering and boundedness problems for vector addition systems”, Rackoff considers a VAS $ (v,A)$ of dimension $ k$ and size $ n$ and derives an upper bound of $ 2^{2^{(\log_2 3)n(\log_2 n)}}$ on the length of nonnegative covering executions.

Let us consider the case $ A\subseteq \{-1,0,+1\}^k$ , $ v\in\mathbb{N}_{\geqslant 0}^k$ and the vector to cover being from $ \{0,1\}^k$ .

What would be a good upper bound on the length of covering nonnegative executions in terms of $ k$ ? Using Rackoff’s Thm. 3.5, $ \lvert A\rvert \leqslant 3^k$ and $ n=\mathcal{O}(3^k+\|v\|_1)$ (where $ \|\cdot\|_1$ returns the 1-norm of a vector) would yield an upper bound of $ 2^{2^{\mathcal{O}(3^k+\|v\|_1)\log_2(3^k+\|v\|_1)}}$ . We need to remove the dependency of the bound on $ v$ and tighten the bound.

It seems to me that a better bound would result from a better bound on $ f(k)$ with respect to $ k$ (rather than to $ n$ ), where $ $ f(0)=1$ $ and $ $ f(i+1)\leqslant (2^n f(i))^{i+1} + f(i)\qquad\text{for $ i\in \mathbb{N}_{\geqslant 0} \cap [0,k[$ }.$ $ Any ideas of how to bound $ f(k)$ by an expression in $ k$ (where $ n$ is dervied from our setup)? If I interpret the proof of Thm. 3.5 correctly, we could probably get something like $ 2^{(3k)^k}$ as an upper bound on the length of covering nonnegative executions. Can you confirm or reject this or provide further ideas or literature citations?