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.
