Languages vs. ω-languages in regular infinite games

Namit Chaturvedi, Jörg Olschewski and Wolfgang Thomas

Abstract. Infinite games are studied in a format where two players, called Player 1 and Player 2, generate a play by building up an ω-word as they choose letters in turn. A game is specified by the ω-language which contains the plays won by Player 2. We analyze ω-languages generated from certain classes K of regular languages of finite words (called ∗-languages), using natural transformations of ∗-languages into ω-languages. Winning strategies for infinite games can be represented again in terms of ∗-languages. Continuing work of Selivanov (2007) and Rabinovich et al. (2007), we analyze how these “strategy ∗-languages” are related to the original language class K. In contrast to that work, we exhibit classes K where strategy representations strictly exceed K.

Comments are closed.