Metafinite Model Theory

Motivated by computer science challenges, we suggest to extend the approach and methods of finite model theory beyond finite structures. We study definability issues and their relation to complexity onmetafinite structureswhich typically consist of (i) a primary part, which is a finite structure, (ii) a secondary part, which is a (usually infinite) structure that can be viewed as a structured domain of numerical objects, and (iii) a set of “weight” functions from the first part into the second. We discuss model-theoretic properties of metafinite structures, present results on descriptive complexity, and sketch some potential applications.

Authors

• Erich Grädel
• Yuri Gurevich

Keywords

No keywords are indexed for this paper.