2026-08-04T08:17:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23530 2025-10-02T12:57:55Z ddc:004 open_access

Reachability in 3-VASS Is Elementary Czerwiński, Wojciech Jecker, Ismaël Lasota, Sławomir Orlikowski, Łukasz vector addition systems Petri nets reachability problem dimension three doubly exponential space length of shortest path The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexity gap by proving the problem to be solvable in doubly-exponential space. The result follows from a new upper bound on the length of the shortest path: if there is a path between two configurations of a 3-VASS then there is also one of at most triply-exponential length. We show it by introducing a novel technique of approximating the reachability sets of 2-VASS by small semi-linear sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wojciech Czerwiński and Ismaël Jecker and Sławomir Lasota and Łukasz Orlikowski 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.153 urn:nbn:de:0030-drops-235307 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.153 eng https://creativecommons.org/licenses/by/4.0/legalcode