Degrees of Lookahead in Context-free Infinite Games

@inproceedings{FLZ11,
  author = {Fridman, Wladimir and L{"o}ding, Christof and Zimmermann, Martin},
  title = {Degrees of {L}ookahead in {C}ontext-free {I}nfinite {G}ames},
  booktitle = {Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =       {264--276},
  series =      {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =        {978-3-939897-32-3},
  ISSN =        {1868-8969},
  year =        {2011},
  volume =      {12},
  editor =      {Marc Bezem},
  publisher =   {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =     {Dagstuhl, Germany},
  URL =         {http://drops.dagstuhl.de/opus/volltexte/2011/3236},
  URN =         {urn:nbn:de:0030-drops-32365},
  doi =         {http://dx.doi.org/10.4230/LIPIcs.CSL.2011.264},
  annote =      {Keywords: infinite games, delay, context-free languages}
  abstract = {We continue the investigation of delay games, infinite games in which one player may postpone her moves for some time to obtain a lookahead on her opponent's moves. We show that the problem of determining the winner of such a game is undecidable for deterministic context-free winning conditions. Furthermore, we show that the necessary lookahead to win a deterministic context-free delay game cannot be bounded by any elementary function. Both results hold already for restricted classes of deterministic context-free winning conditions.}
}