Résumé | Many tasks in computer science can be modelled
by graph games, in which two or more players take turns (or not)
to move a token through a directed graph, tracing out a possibly
infinite path. The objectives of players are given by
properties of infinite paths.
The fundamental mathematical questions on such games
concern the existence of optimal strategies for the
players, the complexity and structural properties
of such strategies, and their realisation by efficient algorithms.
Which games are determined, in the sense that from each
position, one of the players has a winning strategy?
How to compute winning positions and optimal strategies?
How much knowledge on the past of a play is necessary to determine
an optimal next action? Which games are determined by
memoryless strategies? And so on.
These questions are not only mathematically interesting, but
translate into questions of design and verification of
computing systems. The answers strongly depend on the particular
form of a graph game, such as the number of players, the
form of interaction between players (turn based or concurrent),
the information that is available to the players, the
structure of the game graph, and the type of the objectives
or winning conditions of the players.
A well-understood case are two-player, zero-sum games with
perfect information and omega-regular objectives.
In the talk, an overview will be given about fundamental concepts and
results in the algorithmic theory of infinite games,
about connections to other fields such as logic, automata theory, and
verification, and about open problems and new challenges. |