Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów

 

Reachability in Two-Dimensional Vector Addition Systems with States (joint work with Alain Finkel, Stefan Göller, Christoph Haase and Pierre McKenzie)


Seminarium Teoria Automatów

Prelegent: Michael Blondin

2015-05-20 14:15

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.