Graph games with reachability objectives
Chatterjee K. 2011. Graph games with reachability objectives. 5th International Workshop on Reachability Problems. RP: Reachability Problems, LNCS, vol. 6945, 1–1.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Author
Corresponding author has ISTA affiliation
Department
Series Title
LNCS
Abstract
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.
Publishing Year
Date Published
2011-10-15
Proceedings Title
5th International Workshop on Reachability Problems
Publisher
Springer
Volume
6945
Page
1 - 1
Conference
RP: Reachability Problems
Conference Location
Genoa, Italy
Conference Date
2011-09-28 – 2011-09-30
eISSN
IST-REx-ID
Cite this
Chatterjee K. Graph games with reachability objectives. In: 5th International Workshop on Reachability Problems. Vol 6945. Springer; 2011:1-1. doi:10.1007/978-3-642-24288-5_1
Chatterjee, K. (2011). Graph games with reachability objectives. In 5th International Workshop on Reachability Problems (Vol. 6945, pp. 1–1). Genoa, Italy: Springer. https://doi.org/10.1007/978-3-642-24288-5_1
Chatterjee, Krishnendu. “Graph Games with Reachability Objectives.” In 5th International Workshop on Reachability Problems, 6945:1–1. Springer, 2011. https://doi.org/10.1007/978-3-642-24288-5_1.
K. Chatterjee, “Graph games with reachability objectives,” in 5th International Workshop on Reachability Problems, Genoa, Italy, 2011, vol. 6945, pp. 1–1.
Chatterjee K. 2011. Graph games with reachability objectives. 5th International Workshop on Reachability Problems. RP: Reachability Problems, LNCS, vol. 6945, 1–1.
Chatterjee, Krishnendu. “Graph Games with Reachability Objectives.” 5th International Workshop on Reachability Problems, vol. 6945, Springer, 2011, pp. 1–1, doi:10.1007/978-3-642-24288-5_1.