Finite and Algorithmic Model Theory

I.d.R. angeboten in jedem zweiten Wintersemester

• Die Studierenden erlangen Kenntnisse über grundlegende und fortgeschrittene Konzepte aus der Modelltheorie und endlichen Modelltheorie.
• Die Studierenden erlangen Kenntnisse über grundlegende Konzepte aus der Komplexitätstheorie.
• Die Studierenden sind in der Lage, komplexe Aufgaben in Gruppen und selbstständig zu lösen.
• Die Studierenden können erarbeitete Ergebnisse präzise und prägnant präsentieren.
• Die Studierenden sind in der Lage, englische Fachtexte zu verstehen und ihre Ergebnisse auf Englisch zu kommunizieren.

Finite model theory, that is, the model theory of nite structures, has its roots in classical model theory. However, its systematic development was strongly influenced by questions of complexity theory and database theory. In this course we are going to cover the basics of classical first-order and second-order model theory. When restricting to finite structures, the essential theorems, most notably the compactness theorem for first-order logic, fail. We will study the game theoretic methods of Ehrenfeucht and Fraisse that survive and even gain in power over finite models. We then turn our attention to descriptive complexity with the aim to provide machine independent descriptions of important complexity classes. For example, the question whether PTime = PSpace in this theory amounts to the question whether least fixed-point logic has the same expressive power as partial fixed-point logic over finite structures. Finally, we will study locality properties of first-order logic with applications to the algorithmic evaluation and enumeration of queries in relational databases and graphs.

Contents:

• Basic first-order model theory, compactness
• Game characterisations of first-order logic, second-order logic and fixed-point logics
• Game based approaches to model-checking over finite structures
• Basic complexity theory and descriptive complexity
• Model-checking and query evaluation and enumeration over relational databases

• Vorlesungsskript
• Erich Grädel et al. Finite Model Theory and its applications. Springer, 2007.
• Leonid Libkin. Elements of nite model theory. Springer, 2013.
• Heinz-Dieter Ebbinghaus and Jörg Flum. Finite model theory. Springer, 2005.