The Descriptive Complexity of Parity Games
Abstract.
The question of whether the winning regions in parity games can be
computed efficiently is one of the most important open problems in
the field of infinite games. In this talk, I will talk about another
aspect of the complexity of parity games - their logical definability.
I will show how various parameters such as the number of priorities
and whether we consider finite or infinite arenas affect the logical
resources needed to define winning regions. I will also relate this
to the study of Parity games on restricted classes of arenas.