LANGUAGES VERSUS ω-LANGUAGES IN REGULAR INFINITE GAMES
Namit Chaturvedi, Jörg Olschewski, Wolfgang H Thomas · International Journal of Foundations of Computer Science · 2012
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 [Formula: see text] 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 [Formula: see text]. In contrast to that work, we exhibit classes [Formula: see text] where strategy representations strictly exceed [Formula: see text].