Reachability in 3-VASS is Elementary

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

5 lutego 2025 14:15

Pokój

p. 3250

Tytuł w języku polskim

Reachability in 3-VASS is Elementary

Seminarium

Seminarium „Teoria automatów”

---

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.

---