INFINITE GAMES ON FINITELY COLORED GRAPHS WITH APPLICATIONS TO AUTOMATA ON INFINITE-TREES

We examine a class of infinite two-person games on finitely coloured g raphs, The main aim is to construct finite memory winning strategies f or both players. This problem is motivated by applications to finite a utomata on infinite trees. A special attention is given to the exact a mount of memory needed by the players for their winning strategies, Ba sed on a previous work of Gurevich and Harrington and on subsequent im provements of McNaughton we propose a unique framework that allows to reestablish and to improve various results concerning memoryless strat egies due to Emerson and Jutla, Mostowski, Klarlund. (C) 1998-Elsevier Science B.V. All rights reserved.