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

Speaker(s)

Juliusz Straszyński

Affiliation

Uniwersytet Warszawski

Date

Dec. 6, 2017, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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

---