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.


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.