Half-positionally determined winning conditions in infinite games

Prelegent(ci)

Eryk Kopczynski

Afiliacja

Uniwersytet Warszawski

Termin

14 grudnia 2005 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

We consider half-positionally determined winning conditions in infinite games played on a graph by two antagonistic players Eve and Adam. We call a winning condition W _positionally determined_ if, for every infinite game (G,W) using this winning condition, one of the players has a positional (i.e. memoryless) winning strategy. We call a winning condition _half-positionally determined_ if we only require Eve's strategy to be positional, but Adam's strategy can be arbitrary. We will show some general properties of such winning conditions. While some properties of positionally determined conditions can be easily generalized to the case of half-positional determinacy, some cannot. We will also show some classes of half-positionally determined winning conditions; these classes are independent (none of them is included in another) and include: * Concave winning conditions, which, among others, include (generalized) parity conditions and Rabin conditions. Concavity is sufficient for half-positional determinacy only in case of games on finite arenas; * Geometric conditions, associated with convex subsets of [0,1]^n; * Monotonic winning conditions, given by a deterministic finite automaton with a monotonic transition function.

---