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

Improved Lower Bounds for Reachability in Vector Addition Systems

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:19:17Z
dc.abstract.enWe investigate computational complexity of the reachability problem for vector addition systems (or, equivalently, Petri nets), the central algorithmic problem in verification of concurrent systems. Concerning its complexity, after 40 years of stagnation, a non-elementary lower bound has been shown recently: the problem needs a tower of exponentials of time or space, where the height of tower is linear in the input size. We improve on this lower bound, by increasing the height of tower from linear to exponential. As a side-effect, we obtain better lower bounds for vector addition systems of fixed dimension.
dc.affiliationUniwersytet Warszawski
dc.conference.countryWielka Brytania
dc.conference.datefinish2021-07-16
dc.conference.datestart2021-07-12
dc.conference.placeGlasgow
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2021
dc.conference.weblinkhttp://easyconferences.eu/icalp2021/
dc.contributor.authorLasota, Sławomir
dc.contributor.authorCzerwiński, Wojciech
dc.contributor.authorOrlikowski, Łukasz
dc.date.accessioned2024-01-25T03:58:50Z
dc.date.available2024-01-25T03:58:50Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.identifier.doi10.4230/LIPICS.ICALP.2021.128
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/109105
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2021/14197/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages128:1--128:15
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enPetri nets
dc.subject.envector addition systems
dc.subject.enreachability problem
dc.titleImproved Lower Bounds for Reachability in Vector Addition Systems
dc.typeJournalArticle
dspace.entity.typePublication