ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

How Much Memory is Needed to Win Infinite Games?

Stefan Dziembowski and Marcin Jurdzinski and Igor Walukiewicz

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.