How Much Memory is Needed to Win Infinite Games?

Stefan Dziembowski, Marcin Jurdzinski, and Igor Walukiewicz

12th Annual IEEE Symposium on Logic in Computer Science — LICS '97, IEEE, pp. 99–110, Jun 1997.

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.

BibTeX Citation

@inproceedings{DzJuWa97,
    author       = {Stefan Dziembowski and Marcin Jurdzinski and Igor Walukiewicz},
    title        = {How Much Memory is Needed to Win Infinite Games?},
    booktitle    = {12th Annual IEEE Symposium on Logic in Computer Science --- LICS~'97},
    pages        = 99--110,
    year         = 1997,
    month        = 6,
    publisher    = {IEEE},
}