# Reachability in Symmetric VASS

arXiv: https://arxiv.org/abs/2506.23578 · HTML: https://mlsanity.com/paper/2506.23578/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 22 references that are in the map.
- First posted on arXiv 30 Jun 2025.

## Builds on (most cited first, 11 of 11)

- [Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension](https://mlsanity.com/paper/1903.08575/) (2019)
- [The Reachability Problem for Petri Nets is Not Primitive Recursive](https://mlsanity.com/paper/2104.12695/) (2021)
- [The Reachability Problem for Petri Nets is Not Elementary](https://mlsanity.com/paper/1809.07115/) (2018)
- [Reachability in Vector Addition Systems is Ackermann-complete](https://mlsanity.com/paper/2104.13866/) (2021)
- [Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete](https://mlsanity.com/paper/1412.4259/) (2014)
- [Improved Ackermannian lower bound for the Petri nets reachability problem](https://mlsanity.com/paper/2105.08551/) (2021)
- [Equivariant ideals of polynomials](https://mlsanity.com/paper/2402.17604/) (2024)
- [Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes](https://mlsanity.com/paper/2203.04243/) (2022)
- [New Lower Bounds for Reachability in Vector Addition Systems](https://mlsanity.com/paper/2310.09008/) (2023)
- [Improved Algorithm for Reachability in d-VASS](https://mlsanity.com/paper/2404.14781/) (2024)
- [Bi-reachability in Petri nets with data](https://mlsanity.com/paper/2405.16176/) (2024)

## Built on by (most cited first, 1 of 1)

- [Reachability in 3-VAS](https://mlsanity.com/paper/2608.04786/) (2026)

## Abstract (arXiv)

We investigate the reachability problem in symmetric vector addition systems with states (VASS), where transitions are invariant under a group of permutations of coordinates. One extremal case, the trivial groups, yields general VASS. In another extremal case, the symmetric groups, we show that the reachability problem can be solved in PSPACE, regardless of the dimension of input VASS (to be contrasted with Ackermannian complexity in general VASS). We also consider other groups, in particular alternating and cyclic ones. Furthermore, motivated by the open status of the reachability problem in data VASS, we estimate the gain in complexity when the group arises as a combination of the trivial and symmetric groups.