Reachability in 3-VASS is Elementary

Speaker(s)

Wojciech Czerwiński

Affiliation

University of Warsaw

Language of the talk

English

Date

Feb. 5, 2025, 2:15 p.m.

Room

room 3250

Title in Polish

Reachability in 3-VASS is Elementary

Seminar

Seminar Automata Theory

---

I will present our recent result (with Ismael Jecker, Sławomir Lasota and Łukasz Orlikowski)
about the reachability problem in 3-dimensional Vector Addition Systems with States (VASS).
We have shown that the problem is in 2-ExpSpace, before the best known complexity upper bound was Tower.
Our result, roughly speaking, is the first algorithm solving the reachability problem for VASS (in dimension d > 2)
faster than the exhaustive search. To design it we invented novel technique of approximating non-semilinear reachability
sets by semilinear sets. I plan to focus in the talk on the intuition and techniques.

---