In "The covering and boundedness problems for vector addition systems", Rackoff considers a vector addition system $(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 pointwise nonnegative (in author's terminology: "bounded") covering executions.

The paper is from 1978. Have stronger results been proven meanwhile in which, e.g., the constant $\log_2 3$ has been lowered?

Moreover, it seems to me that the same bound $2^{2^{(\log_2 3)n(\log_2 n)}}$ would be obtained using almost the same proof when re-interpreting $n$ as the maximal integer occurring in the addition set of the VAS and in the target to be covered. (As of now, $n$ is the size of the whole VAS.) Can anyone confirm or rejct this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.