← All problems
Unverified

Complexity of fixed VAS reachability

A vector addition system is a finite set of vectors V={v1,v2,…,vn}∈ZdV = \{ v_1,v_2,\ldots,v_n \} \in \mathbb{Z}^d with d∈Nd \in \mathbb{N}. Given two positions s,t∈Nds,t \in \mathbb{N}^d, a run of VV from ss to tt is a sequence s=c0,c1,c2,…,cm=ts = c_0, c_1, c_2, \ldots, c_m = t of positions ci∈Ndc_i \in \mathbb{N}^d where each position is obtained by adding an element of VV to the previous one: ci−ci−1∈Vc_{i} - c_{i-1} \in V for every 1≤i≤m1 \leq i \leq m. Is the following statement correct: Conjecture: For every vector addition system VV, there exists a constant CVC_V such that for every pair of positions ss and tt, if there exists at least one run of VV from ss to tt, one of these runs has a length smaller than CV⋅(∣∣s∣∣+∣∣t∣∣)C_V \cdot \big(||s|| + ||t|| \big).

Coming soon

Organizer

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