The reachability set of every 2-dimensional branching VASS has a computable semilinear representation, so reachability is decidable for this class.
The reachability problem for vector addition systems with a stack is not elementary
1 Pith paper cite this work, alongside 18 external citations. Polarity classification is still indexing.
1
Pith paper citing it
18
external citations · Pith
abstract
By adapting the iterative yardstick construction of Stockmeyer, we show that the reachability problem for vector addition systems with a stack does not have elementary complexity. As a corollary, the same lower bound holds for the satisfiability problem for a two-variable first-order logic on trees in which unbounded data may label only leaf nodes. Whether the two problems are decidable remains an open question.
fields
cs.LO 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
On the Reachability Problem for Two-Dimensional Branching VASS
The reachability set of every 2-dimensional branching VASS has a computable semilinear representation, so reachability is decidable for this class.