Infinite games on finite graphs

Speaker(s)

Thomas COLCOMBET

Affiliation

Uniwersytet w Rennes (Francja), CNRS

Date

Dec. 7, 2005, 2 p.m.

Room

room 2080

Seminar

Seminar Automata Theory

---

Autorskie streszczenie wykladu: We consider games played on an arena (a graph) by two antagonistic players. In such a game, each player, when there is its turn, chooses an edge to follow, originating in the current position. The next position is the destination of this edge. After an infinite number of turns, an infinite path has been chosen, and the winner of the game is decided by checking the conformance of this infinite path to a criterion fixed in advance: the winning condition. Sometimes, the winner of the game can win by playing according to a positional strategy, i.e. a strategy where the next move is decided solely depending on the current position in the game, (and not on the history of the current play). Some winning conditions are known to ensure the existence of a positional strategy for the winner (e.g. parity conditions or mean-payoff conditions over finite arenas). Such situations have important algorithmic impact and deep implications in automata theory. In this talk, we present the basic concepts of this theory of games and aim toward a complete characterization of winning conditions entailing positional strategies for the winner over _finite_ arenas (though we are not able to give a complete answer to this question). This is joint work with Damian Niwinski.

---