You are not logged in | Log in
Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw

Reachability in Vector Addition Systems is Ackermann-complete

Speaker(s)
Wojciech Czerwiński
Affiliation
MIM UW
Date
May 12, 2021, 2:15 p.m.
Information about the event
online
Seminar
Seminar Automata Theory
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.

Careers

Website

© 2024 University of Warsaw. All rights reserved.