# Algorithmic Model Theory

### Summary

Finite model theory studies the relationship between logical definability and computational complexity on finite structures. A particularly important aspect concerns logical descriptions of complexity classes. Our research group has made significant contributions to this area.

A newer development in this field is the extension of the approach and methodology of finite model theory to (particular classes of) infinite structures. Algorithmic issues on infinite structures are of increasing importance in several areas of computer science. In databases, the traditional model based on finite relational structures has turned out to be inadequate for modern applications (like geographic data, constraint databases, data on the Web). Also in verification, infinite (but finitely presentable) transition systems become more and more important, in particular for applications to software.

We investigate several directions, for making the methodology developed in finite model theory applicable to infinite structures. Of particular importance are, again, the connections between algorithmic issues and logical definability.

We have developed a model theory of *metafinite
structures* that combine finite structures with
arithmetic operations on infinite numerical domains.
Applications of metafinite model theory have been studied in
the following domains: descriptive complexity on real
numbers, approximation properties of optimization and
counting problems, databases with uncertain or unreliable
information, and database query languages with aggregates.

We study algorithmic and definability issues on various
classes of infinite structures that are presentable by
*automata* and *interpretations*. The
work by A. Blumensath, V. Bárány, and
E. Grädel on *automatic structures* has
been very influential for the development of this field.

### People

- People working in Finite or Algorithmic Model Theory
- Join the FMT mailing list; subscribe at the FMT mailman page

### Open Problems

- We maintain a collection of Open Problems in Finite Model Theory. (Last updated August 21, 2003.)
- New problems (at most half a page) and announcements of solutions (at most one page) should be sent to Erich Grädel or Dietmar Berwanger, preferably in LaTeX.

### Workshops

#### Almoth

- AlMoTh 2019, Aachen
- AlMoTh 2018, Berlin
- AlMoTh 2017, Dortmund
- AlMoTh 2016, Siegen
- AlMoTh 2015, Bayreuth
- AlMoTh 2014, Kassel
- AlMoTh 2013, Berlin
- AlMoTh 2012, Ilmenau
- AlMoTh 2011, Leipzig
- AlMoTh 2010, Frankfurt
- AlMoTh 2009, Dortmund
- AlMoTh 2008, Freiburg
- AlMoTh 2007, Aachen
- AlMoTh 2006, Aachen
- AlMoTh 2005, Darmstadt

#### Finite and Algorithmic Model Theory

#### Workshop on Logic, Language, Information and Computation

### Contact

Erich Grädel, Dietmar Berwanger, Matthias Hoelzel