Stefan Dziembowski, Marcin Jurdzi{\'n}ski, and Igor Walukiewicz
``How Much Memory Is Needed to Win Infinite Games?''

Abstract:

We consider a class of infinite two-player games played on finitely
coloured graphs.  
Our main question is: 
what is the exact size of memory needed by the players for their
winning strategies.  
This problem is relevant to synthesis of reactive programs and to the
theory of automata on infinite objects.   
Following ideas of Zielonka we provide matching upper and lower bounds
for the size of memory needed by winning strategies in games with a
fixed winning condition.  
We also show that in general the Latest Appearance Record data
structure of Gurevich and Harrington is optimal.