English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Seminal results establish that the coverability problem for Vector AdditionSystems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hardalready under unary encodings (Lipton, '76). More precisely, Rosier and Yenlater utilise Rackoff's bounding technique to show that if coverability holdsthen there is a run of length at most $n^{2^{\mathcal{O}(d \log d)}}$, where$d$ is the dimension and $n$ is the size of the given unary VASS. Earlier,Lipton showed that there exist instances of coverability in $d$-dimensionalunary VASS that are only witnessed by runs of length at least$n^{2^{\Omega(d)}}$. Our first result closes this gap. We improve the upperbound by removing the twice-exponentiated $\log(d)$ factor, thus matchingLipton's lower bound. This closes the corresponding gap for the exact spacerequired to decide coverability. This also yields a deterministic$n^{2^{\mathcal{O}(d)}}$-time algorithm for coverability. Our second result isa matching lower bound, that there does not exist a deterministic$n^{2^{o(d)}}$-time algorithm, conditioned upon the Exponential TimeHypothesis.  When analysing coverability, a standard proof technique is to consider VASSwith bounded counters. Bounded VASS make for an interesting and popular modeldue to strong connections with timed automata. Withal, we study a naturalsetting where the counter bound is linear in the size of the VASS. Here thetrivial exhaustive search algorithm runs in $\mathcal{O}(n^{d+1})$-time. Wegive evidence to this being near-optimal. We prove that in dimension one thistrivial algorithm is conditionally optimal, by showing that $n^{2-o(1)}$-timeis required under the $k$-cycle hypothesis. In general fixed dimension $d$, weshow that $n^{d-2-o(1)}$-time is required under the 3-uniform hypercliquehypothesis.

Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality