PVASS Reachability is Decidable

Speaker(s)

Roland Guttenberg

Affiliation

University of Warsaw

Language of the talk

English

Date

Oct. 8, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

PVASS Reachability is Decidable

Seminar

Seminar Automata Theory

---

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.

---