You are not logged in |
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
- 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.
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.
