The Reachability Problem for Vector Addition Systems is Not Elementary

Speaker(s)

Wojciech Czerwiński

Affiliation

Uniwersytet Warszawski

Date

Oct. 31, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

I will present a recent result about tower lower bound for reachability problem in VASes. I plan to first illustrate a few phenomena occuring in VASes by examples. Then I will show a full proof of the lower bound. This is a joint work with Sławomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki.

---