Making elementary decisions about natural numbers

16^th April 2024, 13:00 6th Floor Conference Room 605, EEE
Dr. Dmitry Chistikov
Department of Computer Science, University of Warwick

Abstract

This talk will offer a brief introduction to logical theories of arithmetic, such as Presburger arithmetic. We will discuss decision procedures (algorithms) for these theories and how they are made "elementary". As an example, we will discuss combining integer programming and a very weak form of exponentiation: a predicate for the set of powers of 2.

Based in part on joint work with Michael Benedikt (Oxford) and Alessio Mansutti (IMDEA Software Institute, Madrid).

Biography

Dmitry Chistikov is an Associate Professor in the Department of Computer Science at the University of Warwick.

Dmitry's research interests lie in theoretical computer science, and in particular in logic and automata theory. Before joining Warwick in 2017, he held postdoctoral positions at Oxford and at the Max Planck Institute for Software Systems. Dmitry completed his PhD degree (Candidate of Sciences) in 2011 at Moscow State University.