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

Speaker(s)

Michael Blondin

Affiliation

ENS Cachan and Université de Montréal

Date

May 20, 2015, 2:15 p.m.

Room

room 5870

Title in Polish

Reachability in Two-Dimensional Vector Addition Systems with States

Seminar

Seminar Automata Theory

---

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.

---