Warsaw University Institute of Philosophy

Programme details

Zofia Adamowicz, "Games in set theory"

Abstract: We shall consider the Steinhaus-Mycielski and Banach-Mazur games. We shall present an introduction to descriptive set theory. Then the notion of a Steinhaus-Mycielski game will be given. We shall show the status of the determiancy assumptions in descriptive set theory. Finally, we shall mention the Banach-Mazur games and their topological aspect.

Peter van Emde Boas, "Games in Computation and Complexity Theory"

Abstract: When in the early 1970-ies Complexity Theory was developed in Computer Science, people would frequently use game models as a tool, particularly in lower-bound arguments. Adversary arguments being a typical example. This was the era where games still belonged either to the field of Economical Science (Game theory), AI (game playing computers) or Recreational Mathematics.
Today the world around games looks quite different. It has become an accepted and well fundable interdisciplinary research topic with interdisciplinary connections with linguistics, sociology, political sciences etc. This workshop itself gives testimony to the tight connections between Games, Logic and Computer Science.
In this tutorial I will present some of the early usages of games in Complexity and Computation theory. We will look in particular into the connections between the fundamental complexity class PSPACE and games, and discuss some ways to remove detours in the argumentations found in the standard literature.
The material is mostly taken from a course called Game Theory for Information Sciences which I have been teaching for the last four years at the UvA; more details about this course and the material on which it is based can be found at the course website: http://staff.science.uva.nl/~peter/teaching/gtis07.html

Henryk Kotlarski, "On some game-theoretic formulas in first order arithmetic"

Abstract: I will present some games related to satisfaction classes in models for arithmetic.

Michał Krynicki, "Ehrenfeucht-Fraïssé games determined by trees"

Abstract: The Ehrenfeucht-Fraïssé game's method is a usefull tool to prove a several kind of undefinability results. Particularly it can be applied to estimate a needed syntactical complexity of a formula expressing a given notion. A typical measure of complexity of a formula are quantifier rank, quantifier type, number of occuring variables and connectives. It is well known that to every of these measures of complexity, except the last one, the game methods can be applied. Now, we modify the Ehrenfeucht-Fraïssé game the be able to apply it to obtain undefinability results estimating a needed number of connectives occuring in a formula. The idea of this modification is to consider an Ehrenfeucht-Fraïssé type game which rules are determined by a given tree. So, the classical Ehrenfeucht-Fraïssé games are peculiar case of such game. We observe that a typical results concerning the Ehrenfeucht-Fraïssé games can be proved in this more general case. We also give some examples of applications of these games to find a lower bound for a number of binary connectives which are needed to express a given notion.

Kerkko Luosto, "Ehrenfeucht-Fraïssé games in finite model theory"

Abstract: A general EF-game for the generalized quantifiers and its application to definability of the Härtig quantifier in linear orders which I presented in LICS2004. There have been plenty of EF-games for generalized quantifiers with some restrictions (monotonicity) or without restriction, but rather involved ones, but it does not seem to be generally known that there is a simple and general way to form an EF-game for a quantifier logic. I could present some history, the game characterization, and an application.