Reachability in Two-Dimensional Vector Addition Systems with States

Prelegent(ci)

Michael Blondin

Afiliacja

ENS Cachan and Université de Montréal

Termin

20 maja 2015 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Alain Finkel, Stefan Göller, Christoph Haase and Pierre McKenzie

Seminarium

Seminarium „Teoria automatów”

---

Known to be decidable since 1981, there still remains a huge gap
between the best known lower and upper bounds for the reachability
problem for vector addition systems with states (VASS). In this talk,
the reachability problem is shown PSPACE-complete in the
two-dimensional case, improving on the doubly exponential time bound established in 1986 by Howell, Rosier, Huynh and Yen.

---