2026-07-20T05:07:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26565 2026-07-01T07:16:15Z ddc:004 open_access

Exploring VASS Parameterised by Geometric Dimension Czerwiński, Wojciech Guttenberg, Roland Orlikowski, Łukasz Sinclair-Banks, Henry Zheng, Yangluo vector addition systems Petri nets geometric dimensions coverability problem integer reachability problem simultaneous unboundedness reachability problem The geometric dimension g of a Vector Addition System with States (VASS) is the dimension of the vector space generated by cycles in the VASS; this parameter refines the standard dimension d, the number of counters. Recently, it was discovered that the fastest-known algorithm for solving the reachability problem for VASS has the same complexity in terms of g as in terms of d. This suggests that the geometric dimension may in fact be a more adequate parameter for measuring the complexity of VASS reachability problems. We initiate a more systematic study of the geometric dimension. We discuss differences between two parameters: the geometric dimension and the SCC dimension. Our main technical result states that classical results about the coverability and boundedness problems can be improved from dimension d to geometric dimension g. Namely, coverability is witnessed by runs of length n^{2^𝒪(g)} instead of n^{2^𝒪(d)}, and unboundedness can be witnessed by runs of length n^{2^𝒪(g log g)} instead of n^{2^𝒪(d log d)}, where n is the size of the instance. We also study integer reachability and simultaneous unboundedness in VASS parameterised by the geometric dimension. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Roland Guttenberg and Łukasz Orlikowski and Henry Sinclair-Banks and Yangluo Zheng 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.177 urn:nbn:de:0030-drops-265655 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.177 eng https://creativecommons.org/licenses/by/4.0/legalcode