← All problems
Unverified

Fine Grained Complexity for VAS Boundedness

A (dd-dimensional) Vector Addition System is a set of vectors T⊆ZdT \subseteq \mathbb Z^d and induces a single-step transition relation → ⊆Nd×Nd\mathrm\rightarrow\ \subseteq \mathbb N^d \times \mathbb N^d by u→v⇔v=u+t\mathbf u \rightarrow \mathbf v \Leftrightarrow \mathbf v = \mathbf u + \mathbf t for some t∈T\mathbf t \in T. The transitive closure of →\rightarrow, →∗\rightarrow^*, is called the reachability relation and for some vector u∈Nd\mathbf u \in \mathbb N^d, we call R(u)={v∣u→∗v}R(\mathbf u) = \{\mathbf v \mid \mathbf u \rightarrow^* \mathbf v\} the reachability set of u\mathbf u. The boundedness problem for VAS asks if, given a vector u\mathbf u, the set R(u)R(\mathbf u) is finite. It has been long known that the boundedness problem for VAS is EXPSPACE-complete. A more careful analysis reveals an upper bound of O(n2dlog⁡d)\mathcal O(n^{2^{d \log d}}). A similar upper bound for VAS coverability was recently tightened to O(n2d)\mathcal O(n^{2^d}). Can we tighten the upper bound for boundedness too?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu