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 0-1 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 Ehrenfeucht-Fraisse 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 SQL-like or XPath-like 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 domain-specific language.

Literature

  • Heinz-Dieter 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 978-0-12-238452-3
  • Wilfrid Hodges. Model theory, Cambridge University Press, Cambridge 1993, 772pp.