You are not logged in | Log in

Half-positionally determined winning conditions in infinite games

Speaker(s)
Eryk Kopczynski
Affiliation
Uniwersytet Warszawski
Date
Dec. 14, 2005, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

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.