News and events archive

Informatics colloquium 17. 10. 2017, 14:00 lecture hall D2 Dr. rer. nat. Achim Blumensath, FI MU Algorithmic Model Theory Abstract: Tools from logic are used in many areas of contemporary computer science including databases, verification, and algorithms and complexity. The field of algorithmic model theory developed in response to these applications. It studies the various logics used by applications with a focuses on two related aspects: (i) algorithmic questions, in particular algorithms for the model checking problem; and (ii) questions concerning the expressive power of these logics. In this talk I will give an overview over the various aspects of algorithmic model theory and then concentrate on a few selected areas. A recurring topic will be the notion of a compatible operation. We will discuss several applications of such operations throughout algorithmic model theory. As a more detailed example I will present a classification theorem for a particular kind of operations called a transductions.