Abstract
Delay games are two-player games of infinite duration in which one player may delay her moves to obtain a lookahead on her opponent’s moves. For \(\omega \)-regular winning conditions it is known that such games can be solved in doubly-exponential time and that doubly-exponential lookahead is sufficient.
We improve upon both results by giving an exponential time algorithm and an exponential upper bound on the necessary lookahead. This is complemented by showing \(\textsc {ExpTime}\)-hardness of the solution problem and tight exponential lower bounds on the lookahead. Both lower bounds already hold for safety conditions. Furthermore, solving delay games with reachability conditions is shown to be \(\textsc {PSpace}\)-complete.
Partially supported by the DFG projects “TriCS” (ZI 1516/1-1) and “AVACS” (SFB/TR 14). The first author was supported by an IMPRS-CS PhD Scholarship.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Büchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Trans. Amer. Math. Soc. 138, 295–311 (1969)
Carayol, A., Löding, C.: MSO on the infinite binary tree: choice and order. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 161–176. Springer, Heidelberg (2007)
Carayol, A., Löding, C.: Uniformization in automata theory. In: Schroeder-Heister, P., Heinzmann, G., Hodges, W., Bour, P.E. (eds.) CLMPS. College Publications, London (2012) (to appear)
Chandra, A.K., Kozen, D., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114–133 (1981)
Fridman, W., Löding, C., Zimmermann, M.: Degrees of lookahead in context-free infinite games. In: Bezem, M. (ed.) CSL 2011. LIPIcs, vol. 12, pp. 264–276. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)
Gurevich, Y., Shelah, S.: Rabin’s uniformization problem. The Journal of Symbolic Logic 48, 1105–1119 (1983)
Holtmann, M., Kaiser, L., Thomas, W.: Degrees of lookahead in regular infinite games. LMCS 8(3) (2012)
Hosch, F.A., Landweber, L.H.: Finite delay solutions for sequential conditions. In: ICALP 1972, pp. 45–60 (1972)
Hutagalung, M., Lange, M., Lozes, É.: Buffered simulation games for Büchi automata. In: Ésik, Z., Fülöp, Z. (eds.) AFL 2014. EPTCS, vol. 151, pp. 286–300 (2014)
Klein, F., Zimmermann, M.: How much lookahead is needed to win infinite games? (2014). arXiv: 1412.3701
Klein, F., Zimmermann, M.: What are strategies in delay games? Borel determinacy for games with lookahead (2015). arXiv: 1504.02627
Löding, C., Winter, S.: Synthesis of deterministic top-down tree transducers from automatic tree relations. In: Peron, A., Piazza, C. (eds.) GandALF 2014. EPTCS, vol. 161, pp. 88–101 (2014)
Schewe, S.: Solving parity games in big steps. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 449–460. Springer, Heidelberg (2007)
Thomas, W., Lescow, H.: Logical specifications of infinite computations. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1993. LNCS, vol. 803, pp. 583–621. Springer, Heidelberg (1994)
Trakhtenbrot, B., Barzdin, I.: Finite Automata; Behavior and Synthesis. Fundamental Studies in Computer Science, vol. 1. North-Holland Publishing Company, New York. American Elsevier (1973)
Zimmermann, M.: Delay games with WMSO+U winning conditions. In: CSR 2015 (2015, to appear). arXiv: 1412.3978
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Klein, F., Zimmermann, M. (2015). How Much Lookahead is Needed to Win Infinite Games?. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9135. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47666-6_36
Download citation
DOI: https://doi.org/10.1007/978-3-662-47666-6_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47665-9
Online ISBN: 978-3-662-47666-6
eBook Packages: Computer ScienceComputer Science (R0)