3
$\begingroup$

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?

$\endgroup$

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.