3
$\begingroup$

In 1976–1977, Rackoff proved in The covering and boundedness problems for vector addition systems that the length of a shortest covering sequence in a VAS is bounded by $2^{(3n)^n} = 2^{2^{(\log_2 3)n\log_2 n}}$, where $n$ is the input size. Is this upper bound still the best known one in general or has it been tightened (e.g., to something like $2^{(dn)^n}$ for $d<3$) in the meantime? I searched for improvements in the literature but have not discovered anything.

$\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.