2026-07-23T03:50:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24167 2025-11-12T13:33:58Z ddc:004 open_access

Reachability in Symmetric VASS Kamiński, Łukasz Lasota, Sławomir vector addition systems Petri nets reachability problem symmetry permutation group 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Łukasz Kamiński and Sławomir Lasota 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.60 urn:nbn:de:0030-drops-241678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.60 eng https://creativecommons.org/licenses/by/4.0/legalcode