When: October 3, 2pm

Where: room G2.91b

Abstract

We consider two-player games played on graphs with omega-regular objectives. We classify these games according to the observation of the players and on the presence of randomisation in the game. On the basis of information, the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and © complete-observation (both players have complete view of the game). We consider various classes of strategies defined according to the information available to the players and to their power of randomization. We survey and present recent results that characterize the memory requirement for the different classes of strategies to win in various classes of two-player games according to the classification.