| ||||
| ||||
![]() Title:Exploring VASS Parameterised by Geometric Dimension Authors:Wojciech Czerwiński Conference:Highlights26 Tags:boundedness problem, coverability problem, exponential space, geometric dimension and vector addition systems Abstract: Typically problems for Vector Addition Systems with States (VASS) are parametrized by its number of counters (let us denote it by d). I will analyse another parameter called geometric dimension g, which is the dimension of the linear space spanned by effects of cycles in VASS. Notice that clearly g ≤ d. It was recently noticed that the current best algorithm for the reachability problem in VASS working in F_d also works in F_g, so substantially better if g is much smaller than d. I will present results showing that the current best known results for other classical problems, namely coverability, boundedness, simultaneous unbdoundedness and integer reachability also behave similarly when parametrised by g instead of being parametrised by d. The presentation is based on the paper accepted to ICALP 2026, co-authored by Roland Guttenberg, Łukasz Orlikowski, Henry Sinclair-Banks and Yangluo Zheng. Exploring VASS Parameterised by Geometric Dimension ![]() Exploring VASS Parameterised by Geometric Dimension | ||||
| Copyright © 2002 – 2026 EasyChair |
