Evènement pour le groupe Séminaire du LaBRI

Date 2006-11-09  14:00-15:00
TitreHow to win infinite games? 
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. 
LieuAmphi 050 
OrateurErich Graedel 

Aucun document lié à cet événement.

Retour à l'index