EADS talk by Dmitry Chistikov

On 10 August 2017, Dmitry Chistikov, Assistant Professor at the University of Warwick, UK, will give a talk at DIKU.

Ultimately periodic sets, Presburger arithmetic, and integer programming with quantifiers

How to generalize ultimately periodic sets of natural numbers to several dimensions? An answer to this question is the definition of semi-linear sets. These sets coincide with the sets definable in Presburger arithmetic, the first-order theory of the natural numbers with addition and order.

In this talk, I will give a brief survey of semi-linear sets and Presburger arithmetic, illustrating classic techniques and results. I will also sketch, as a recent application, a proof that integer programming with k quantifier blocks is complete for the kth level of the polynomial hierarchy.

Partly based on joint work with Christoph Haase.


Dmitry Chistikov is an assistant professor at the University of Warwick, UK. His research interests lie in automata theory, verification, and theoretical computer science. He previously held postdoctoral appointments at the University of Oxford, UK, and at the Max Planck Institute for Software Systems (MPI-SWS) in Kaiserslautern, Germany. He obtained his PhD in 2011 from Moscow State University, Russia.