Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:50:13Z
dc.abstract.enWe study the complexity of the reachability problem for Vector Addition Systems with States (VASSes) in fixed dimensions. We provide four lower bounds improving the currently known state-of-the-art: 1) NP-hardness for unary flat 4-VASSes (VASSes in dimension 4), 2) PSpace-hardness for unary 5-VASSes, 3) ExpSpace-hardness for binary 6-VASSes and 4) Tower-hardness for unary 8-VASSes.
dc.affiliationUniwersytet Warszawski
dc.conference.countryIzrael
dc.conference.datefinish2022-08-05
dc.conference.datestart2022-08-02
dc.conference.placeHaifa
dc.conference.seriesIEEE Symposium on Logic in Computer Science
dc.conference.seriesIEEE Symposium on Logic in Computer Science
dc.conference.seriesshortcutLICS
dc.conference.shortcut37'th LICS
dc.conference.weblinkhttps://lics.siglog.org/lics22/
dc.contributor.authorOrlikowski, Łukasz
dc.contributor.authorCzerwiński, Wojciech
dc.date.accessioned2024-01-25T05:25:01Z
dc.date.available2024-01-25T05:25:01Z
dc.date.issued2022
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.1145/3531130.3533357
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/111549
dc.identifier.weblinkhttps://dl.acm.org/doi/pdf/10.1145/3531130.3533357
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages40: 1–12
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.envector addition systems
dc.subject.enreachability problem
dc.subject.enlower bounds
dc.subject.enPetri nets
dc.titleLower Bounds for the Reachability Problem in Fixed Dimensional VASSes
dc.typeJournalArticle
dspace.entity.typePublication