MATH EXPLORERS' CLUB Cornell Department of Mathematics 

Ehrenfeucht-Fraïssé games



The books by Leonid Libkin on finite model theory provide an excellent introduction to Ehrenfeucht-Fraïssé games. The history of Ehrenfeucht-Fraïssé games presented in the first lesson comes from the last source, Logic and games, (Stanford Encyclopedia of Philosophy). For applications of the Ehrenfeucht-Fraïssé metodology to proving inexpressibility results in database query languages, a great source are professor Cristoph Koch's lecture notes on Database Systems. In particular the decision trees in this module come from his lessons.

  1. E. Gradel, P. Kolaitis, L. Libkin, Finite Model Theory and Its Applications, Springer-Verlag 2007.
  2. L. Libkin Elements of Finite Model Theory, Springer-Verlag 2004.
  3. Cristoph Koch, Lecture notes in Database Systems course, Cornell University, Spring 2009.
  4. Ehrenfeucht-Fraïssé games, Wikipediaïssé_game
  5. Logic and Games (Stanford Encyclopedia of Philosophy)

Top Next lesson