Lectures: Finite Model Theory
Summer term. Last update: 2024-01-04.
This is a joint lecture for Czech and English students students of the Czech Technical University.
The full information about the course is available in KOS and regular updates about the course will appear on courses.fit.cvut.cz (a login needed for both).
Overview
- Course overview, motivation and relation to the theory of database systems
- Ehrenfeucht-Fraı̈ssé games
- Inexpressibility theorems in first-order logic
- Hanf’s locality theorem
- Gaifman’s locality theorem
- Descriptive complexity and second-order logic
- Logics with the ability to calculate
- Turing machines and finite models
- Logics with a finite number of variables
- Constraints satisfaction problem and logic
- Game comonads and one-way games
- Coalgebras of game comonads
- Game Comonads and Logic
References
- Leonid Libkin. Elements of Finite Model Theory. Springer-Verlag 2004.
- Heinz-Dieter Ebbinghaus, Jörg Flum. Finite Model Theory: Second Edition. Springer-Verlag 1995.
- Szymon Toruńczyk. Lectures on Finite Model Theory, University of Warsaw, 2022. https://duch.mimuw.edu.pl/~szymtor/fmt.pdf
- Erich Gradel, Phokion Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y Vardi, Yde Venema, Scott Weinstein. Finite Model Theory and Its Applications. Springer-Verlag 2007.
- Samson Abramsky, Nihil Shah. Relating Structure and Power, Comonadic Semantics for Computational Resources. Journal of Logic and Computation, 2021.
- Samson Abramsky, Anuj Dawar, Pengming Wang. The pebbling comonad in Finite Model Theory. 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) 2017.