Reachability in symmetric VASS

Prelegent(ci)

Łukasz Kamiński

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

30 kwietnia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Reachability in symmetric VASS

Seminarium

Seminarium „Teoria automatów”

---

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. 

---