PVASS Reachability is Decidable

Prelegent(ci)

Roland Guttenberg

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

8 października 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

PVASS Reachability is Decidable

Seminarium

Seminarium „Teoria automatów”

---

Reachability in pushdown vector addition systems with states (PVASS) used to be among the longest standing open problems in Theoretical Computer Science. The PVASS reachability problem consists of deciding whether the intersection of a VASS language and a context-free language is empty.

Roland Meyer, Eren Keskin and I have recently proven this problem to be decidable. In this talk I will sketch some of the main ideas of the corresponding algorithm.

---