Exploring VASS Parameterised by Geometric Dimension
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908837576966144 |
|---|---|
| author | Czerwiński, Wojciech Guttenberg, Roland Orlikowski, Łukasz Sinclair-Banks, Henry Zheng, Yangluo |
| author_facet | Czerwiński, Wojciech Guttenberg, Roland Orlikowski, Łukasz Sinclair-Banks, Henry Zheng, Yangluo |
| contents | The geometric dimension $g$ of a Vector Addition System with States (VASS) is the dimension of the vector space generated by cycles in the VASS; this parameter refines the standard dimension $d$, the number of counters. Recently, it was discovered that the fastest-known algorithm for solving the reachability problem for VASS has the same complexity in terms of $g$ as in terms of $d$. This suggests that the geometric dimension may in fact be a more adequate parameter for measuring the complexity of VASS reachability problems. We initiate a more systematic study of the geometric dimension. We discuss differences between two parameters: the geometric dimension and the SCC dimension. Our main technical result states that classical results about the coverability and boundedness problems can be improved from dimension $d$ to geometric dimension $g$. Namely, coverability is witnessed by runs of length $n^{2^{\mathcal{O}(g)}}$ instead of $n^{2^{\mathcal{O}(d)}}$, and unboundedness can be witnessed by runs of length $n^{2^{\mathcal{O}(g\log g)}}$ instead of $n^{2^{\mathcal{O}(d\log d )}}$, where $n$ is the size of the instance. We also study integer reachability and simultaneous unboundedness in VASS parameterised by the geometric dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15483 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exploring VASS Parameterised by Geometric Dimension Czerwiński, Wojciech Guttenberg, Roland Orlikowski, Łukasz Sinclair-Banks, Henry Zheng, Yangluo Formal Languages and Automata Theory F.1.1 The geometric dimension $g$ of a Vector Addition System with States (VASS) is the dimension of the vector space generated by cycles in the VASS; this parameter refines the standard dimension $d$, the number of counters. Recently, it was discovered that the fastest-known algorithm for solving the reachability problem for VASS has the same complexity in terms of $g$ as in terms of $d$. This suggests that the geometric dimension may in fact be a more adequate parameter for measuring the complexity of VASS reachability problems. We initiate a more systematic study of the geometric dimension. We discuss differences between two parameters: the geometric dimension and the SCC dimension. Our main technical result states that classical results about the coverability and boundedness problems can be improved from dimension $d$ to geometric dimension $g$. Namely, coverability is witnessed by runs of length $n^{2^{\mathcal{O}(g)}}$ instead of $n^{2^{\mathcal{O}(d)}}$, and unboundedness can be witnessed by runs of length $n^{2^{\mathcal{O}(g\log g)}}$ instead of $n^{2^{\mathcal{O}(d\log d )}}$, where $n$ is the size of the instance. We also study integer reachability and simultaneous unboundedness in VASS parameterised by the geometric dimension. |
| title | Exploring VASS Parameterised by Geometric Dimension |
| topic | Formal Languages and Automata Theory F.1.1 |
| url | https://arxiv.org/abs/2602.15483 |