Reachability in Vector Addition Systems is Ackermann-complete

Prelegent(ci)

Wojciech Czerwiński

Afiliacja

MIM UW

Termin

12 maja 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

Complexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problem for a few decades. Very recently two proofs of Ackermann-hardness were obtained independently (one by Jerome Leroux, one by us). I will present you the proof obtained in a joint work with Łukasz Orlikowski. The proof is based mostly on one new technique proposed in the paper: possibility of performing many zero-tests in VASes by use of just one additional counter.

---