2026-08-17T06:34:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18545 2024-03-06T11:02:05Z ddc:004 open_access

The Geometry of Reachability in Continuous Vector Addition Systems with States Almagor, Shaull Ghosh, Arka Leys, Tim Pérez, Guillermo A. Vector addition system with states reachability continuous approximation We study the geometry of reachability sets of continuous vector addition systems with states (VASS). In particular we establish that they are "almost" Minkowski sums of convex cones and zonotopes generated by the vectors labelling the transitions of the VASS. We use the latter to prove that short so-called linear path schemes suffice as witnesses of reachability in continuous VASS. Then, we give new polynomial-time algorithms for the reachability problem for linear path schemes. Finally, we also establish that enriching the model with zero tests makes the reachability problem intractable already for linear path schemes of dimension two. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shaull Almagor and Arka Ghosh and Tim Leys and Guillermo A. Pérez 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.11 urn:nbn:de:0030-drops-185457 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.11 eng https://creativecommons.org/licenses/by/4.0/legalcode