Reachability in symmetric VASS

Speaker(s)

Łukasz Kamiński

Affiliation

University of Warsaw

Language of the talk

English

Date

April 30, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Reachability in symmetric VASS

Seminar

Seminar Automata Theory

---

We investigate the reachability problem in symmetric 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 open status of the reachability problem in data VASS, we estimate the gain in complexity when the group arises as a combination of trivial and symmetric group. 

---