Nie jesteś zalogowany |
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
- 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.
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.
