2026-07-24T11:17:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23988 2025-11-12T13:25:19Z ddc:004 open_access

Reachability in Vector Addition System with States Parameterized by Geometric Dimension Zheng, Yangluo Petri net vector addition system reachability geometric dimension pumping The geometric dimension of a vector addition system with states (VASS), emerged in Leroux and Schmitz (2019) and formalized by Fu, Yang, and Zheng (2024), quantifies the dimension of the vector space spanned by cycle effects in the system. This paper examines the VASS reachability problem through the lens of geometric dimension, revealing key differences from the traditional dimensional parameterization. Notably, we establish that the reachability problem for both geometrically 1-dimensional and 2-dimensional VASS is PSPACE-complete, achieved by extending the pumping technique initially proposed by Czerwiński et al. (2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yangluo Zheng 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.38 urn:nbn:de:0030-drops-239888 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.38 eng https://creativecommons.org/licenses/by/4.0/legalcode