Metafinite Model Theory

Erich Graedel

This talk will be an introduction and survey on the algorithmic and model theoretic properties of metafinite structures that have been introduced twenty years ago in joint work with Yuri Gurevich. Metafinite structures consist of a primary part which is a finite structure, a secondary part which is a (usually infinite) domain of numerical objects with arithmetic functions, and a set of weight functions from the first part into the second.

An important motivation for the study of metafinite structures has been the extension of the approach and methods of finite model theory to this richer setting that is relevant for many applications in computer science.