@inproceedings{3357,
  abstract     = {We consider two-player graph games whose objectives are request-response condition, i.e conjunctions of conditions of the form "if a state with property Rq is visited, then later a state with property Rp is visited". The winner of such games can be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we close this gap by showing that this problem is, in fact, EXPTIME-complete. We show that the problem becomes PSPACE-complete if we only consider games played on DAGs, and NP-complete or PTIME-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition). We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.},
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Horn, Florian},
  editor       = {Dediu, Adrian-Horia and Inenaga, Shunsuke and Martín-Vide, Carlos},
  location     = {Tarragona, Spain},
  pages        = {227 -- 237},
  publisher    = {Springer},
  title        = {{The complexity of request-response games}},
  doi          = {10.1007/978-3-642-21254-3_17},
  volume       = {6638},
  year         = {2011},
}