Graph Games with Reachability Objectives

Games played on graphs provide the mathematical framework to analyze several important problems in computer science as well as mathematics, such as the synthesis problem of Church, model checking of open reactive systems and many others. On the basis of mode of interaction of the players these games can be classified as follows: (a)

turn-based

(players make moves in turns); and (b)

concurrent

(players make moves simultaneously). On the basis of the information available to the players these games can be classified as follows: (a)

perfect-information

(players have perfect view of the game); and (b)

partial-information

(players have partial view of the game). In this talk we will consider all these classes of games with

reachability

objectives, where the goal of one player is to reach a set of target vertices of the graph, and the goal of the opponent player is to prevent the player from reaching the target. We will survey the results for various classes of games, and the results range from linear time decision algorithms to EXPTIME-complete problems to undecidable problems.