Aktualności — Wydarzenia
Automata Theory
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.
2015-05-18
Wojciech Czerwiński
You are not logged in | log in
