35 citations · 169 across the 13 of their papers we have counts for
4 papers · 1 filter
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete
Michael Blondin, Alain Finkel, Stefan Göller +2
Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidabl…
The Odds of Staying on Budget
Christoph Haase, Stefan Kiefer
Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with non-negative integer costs, we study the computational complexity of deciding whether t…
Integer Vector Addition Systems with States
Christoph Haase, Simon Halfon
This paper studies reachability, coverability and inclusion problems for Integer Vector Addition Systems with States (ZVASS) and extensions and restrictions thereof. A ZVASS compri…
Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy
Christoph Haase
It is shown that for any fixed , the -fragment of Presburger arithmetic, i.e., its restriction to quantifier alternations beginning with an existential quantifi…