← All problems
Unverified

Bounds on the length of a coverability path in VASS

By the classic Rackoff argument in d-dimensional Vector Addition System with States (d-VASS) V if there is a path starting in configuration s and covering configuration t then there is also a covering path of length at most M k , where M is the maximal number occurring on transitions of VASS and in configurations s and t, while k≈2dk \approx 2^d. Therefore for each fixed d there is a path of length polynomial in M. We conjecture that a much stronger property holds, that there is always a covering path of length f(size(V))⋅(size(s)+size(t)f(size(V)) \cdot (size(s) + size(t), namely depending in some way on the size of VASS V, but only linear with respect to the size of source s and target t. I think this conjecture is hard to prove despite of a simple formulation and progress on it could led to a deep understanding of runs of VASS.

Coming soon

Organizer

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