mlsanityData to 14 Oct 2026

Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes

arXiv 2203.04243 ↗First posted 8 Mar 2022cs.FL cs.LOcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 8 Mar 2022.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Reachability in Symmetric VASScited by 1