Graph games with reachability objectives

K. Chatterjee, in:, G. Delzanno, I. Potapov (Eds.), Springer, 2011, pp. 1–1.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Editor
;
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
Volume
6945
Page
1 - 1
Conference
RP: Reachability Problems
Conference Location
Genoa, Italy
Conference Date
2011-09-28 – 2011-09-30
IST-REx-ID

Cite this

Chatterjee K. Graph games with reachability objectives. In: Delzanno G, Potapov I, eds. Vol 6945. Springer; 2011:1-1. doi:10.1007/978-3-642-24288-5_1
Chatterjee, K. (2011). Graph games with reachability objectives. In G. Delzanno & I. Potapov (Eds.) (Vol. 6945, pp. 1–1). Presented at the RP: Reachability Problems, Genoa, Italy: Springer. https://doi.org/10.1007/978-3-642-24288-5_1
Chatterjee, Krishnendu. “Graph Games with Reachability Objectives.” edited by Giorgo Delzanno and Igor Potapov, 6945:1–1. Springer, 2011. https://doi.org/10.1007/978-3-642-24288-5_1.
K. Chatterjee, “Graph games with reachability objectives,” presented at the RP: Reachability Problems, Genoa, Italy, 2011, vol. 6945, pp. 1–1.
Chatterjee K. 2011. Graph games with reachability objectives. RP: Reachability Problems, LNCS, vol. 6945. 1–1.
Chatterjee, Krishnendu. Graph Games with Reachability Objectives. Edited by Giorgo Delzanno and Igor Potapov, vol. 6945, Springer, 2011, pp. 1–1, doi:10.1007/978-3-642-24288-5_1.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar