What kind of memory is needed to win infinitary Muller games?
Erich Grädel, Łukasz Kaiser · RWTH Publications (RWTH Aachen) · 2007
In an influential paper entitled "How much memory is needed to win infinite games", Dziembowski, Jurdziński, and Walukiewicz have shown that there are Muller games of size O(n) whose winning strategies require memory of size at least n!.This shows that the LAR-memory, based on the latest appearance records introduced by Gurevich and Harrington, is optimal for solving Muller games.We review these results and reexamine the situation for the case of infinitary Muller games, i.e.Muller games with infinitely many priorities.We introduce a new, infinite, memory structure, based on finite appearance records (FAR) and investigate classes of Muller games that can be solved with FARmemory.