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

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

Pokaż widok metadanych
DOI
10.1145/3531130.3533357
Autor
Orlikowski, Łukasz
Czerwiński, Wojciech
Data publikacji
2022
Abstrakt (EN)

We 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.

Słowa kluczowe EN
vector addition systems
reachability problem
lower bounds
Petri nets
Dyscyplina PBN
informatyka
Strony od-do
40: 1–12
Link do źródła
https://dl.acm.org/doi/pdf/10.1145/3531130.3533357
Licencja otwartego dostępu
Dostęp zamknięty