PSPACE-complexity of reachability and coverability problems for acyclic Grammar VASes

Prelegent(ci)

Juliusz Straszyński

Afiliacja

Uniwersytet Warszawski

Termin

6 grudnia 2017 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

I will show a reduction of reachablity problem for Grammar VASes to a Subset Sum Game, which is PSPACE-complete.

---