Current Trends in Theory and Practice of Computer Science  
Track filter:   
Invited Talk
Foundations of Computer Science

Sunday, January 20, 8:30 - 10:00

Wolfgang Thomas

Optimizing Winning Strategies in Regular Infinite Games

We consider infinite two-player games played on infinite graphs where the winning condition (say for the first player) is given by a regular omega-language. We recall the fundamentals for "solving" such games, in particular for synthesizing finite automata that realize winning strategies. In the remainder of the talk we address issues of optimization which are essential in practical applications (e.g. controller synthesis). We focus on two aspects: minimization of the memory size of automata that execute winning strategies, and - for games with liveness requests as winning conditions - minimization of the "waiting times" for the satisfaction of requests.

pdf iconPresentation (467 kB)
SOFSEM 2008, January 19-25, High Tatras, Slovakia