Introduction to Finite Model Theory
Contents
This lecture is a logical continuation of and supplement to GLoIn.
Lernziele und Kompetenzen
Wissen  The students will learn basic notions and results of finite model theory 

Verstehen  The students will be able to summarize and prove major results of finite model theory and explain the deep difference between finite and infinite model theory, by using 01 laws or by showing the failure of most preservation theorems 
Anwenden  The students will be able to use basic tools of finite model theory, such as EhrenfeuchtFraisse games or Herbrand structures. The students will use preservation theorems of Rosen or Rossman to characterize expressive power of logics over finite structures 
Analysieren  The students will be able to determine, e.g., whether a given SQLlike or XPathlike query is expressible over all finite models (or restricted subclasses of structures) in a chosen language 
Evaluieren (Beurteilen)  The best students, having gained a deep understanding of finite model theory, will be able to examine and evaluate choices involved in designing a language, with particular attention to the criterion of expressive completeness and contrasting expressive power of a given language with its computational complexity 
Erschaffen  Making the right design choices is an important skill whenever the need arises for a new domainspecific language. 
Literature

HeinzDieter Ebbinghaus, Jörg Flum. Finite Model Theory, Springer, preferably edition 1999

Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi. Finite Model Theory and its Applications, EATCS Series: Texts in Theoretical Computer Science, Springer 2007

Leonid Libkin. Elements of Finite Model Theory, Springer 2012
———–Supplementary reading on logic and classical (unrestricted) model theory———

Herbert B. Enderton. A Mathematical Introduction to Logic (1 ed. 1972). Academic Press Second edition, 2001. ISBN 9780122384523

Wilfrid Hodges. Model theory, Cambridge University Press, Cambridge 1993, 772pp.