Autor:	Czerwiński, Wojciech, Orlikowski, Łukasz
Rok vydání:	2022
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Logic in Computer Science
Druh dokumentu:	Working Paper
Popis:	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.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2203.04243 Zobrazit plný text záznamu View this record from Arxiv