Take-home exam

Here is a draft the final version of the first part of the take-home exam .

Lesson 7: definable graph games

Sets definable in a first-order theory. Definable graphs and reachability problems.

Lesson 6: constraint logic

Bounded and undounded zero-player constraint logic games. Bounded single player constraint logic game (NP-complete). Bounded two-player constraint logic game (PSPACE-complete).

Lesson 4/5: games with Muller condition

Equivalence between non-deterministic Buchi and both deterministic and non-deterministic Muller automata. Equivalence between deterministic Muller and deterministic parity automata. Finite memory strategies. Finite memory strategy for Muller games.

Lesson 3: a fool who became wise

We learned about inverse image, direct image and dual image functions and how they relate modal operators. We also investigated an infinite variant of Chomp game. The following note gives a proof of the Fundamental Theorem of Chomp Game. Notice that in our notation we implicitly assumed that n is finite, but it is not relevant for the proof.

Lesson 2: no more basis

We recalled some basic information from Set Theory (a poset is complete iff it is cocomplete; general fixed point via transfinite induction, fixed points in finite posets, fixed points of cocontinuous functions). The following note shows that if we assume a very weak form of axiom of determinacy then the space 2N over the field of characteristic 2 does not have any basis. Moreover, from any basis of 2N we construct an indetermined word game, whose outcome does not depend on only finite sequence of moves.

Lesson 1: introduction

During the first lesson we examined simple mathematical games: Chomp, Nim, Hex. Moreover, we investigated winning strategies in Choquet games (over real line, rational line and irrational line).