Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

The Geometry of Reachability in Continuous Vector Addition Systems with States

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:36:54Z
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryFrancja
dc.conference.datefinish2023-09-01
dc.conference.datestart2023-08-28
dc.conference.placeBordoux
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesshortcutMFCS
dc.conference.shortcut(MFCS 2023)
dc.contributor.authorPérez, Guillermo A.
dc.contributor.authorLeys, Tim
dc.contributor.authorGhosh, Arka
dc.contributor.authorAlmagor, Shaull
dc.date.accessioned2024-01-26T10:15:00Z
dc.date.available2024-01-26T10:15:00Z
dc.date.copyright2023-08-21
dc.date.issued2023
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.MFCS.2023.11
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/122368
dc.identifier.weblinkhttps://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.11
dc.languageeng
dc.relation.pages1-13
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleThe Geometry of Reachability in Continuous Vector Addition Systems with States
dc.typeJournalArticle
dspace.entity.typePublication