Abstract
We study infinite games where one of the players always has a positional (memory-less) winning strategy, while the other player may use a history-dependent strategy. We investigate winning conditions which guarantee such a property for all arenas, or all finite arenas. We establish some closure properties of such conditions, and discover some common reasons behind several known and new positional determinacy results. We exhibit several new classes of winning conditions having this property: the class of concave conditions (for finite arenas) and the classes of monotonic conditions and geometrical conditions (for all arenas).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Walukiewicz, I., Bouquet, A.-J., Serre, O.: Pushdown Games with Unboundedness and Regular Conditions. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 88–99. Springer, Heidelberg (2003)
Cachat, T., Duparc, J., Thomas, W.: Pushdown games with a Σ3 winning condition. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol. 2471, pp. 322–336 (2002)
Colcombet, T., Niwiński, D.: On the positional determinacy of edge-labeled games. Theor. Comput. Sci. 352, 190–196 (2006)
Emerson, E.A., Jutla, C.S.: Tree automata, mu-calculus and determinacy. In: Proceedings 32th Annual IEEE Symp. on Foundations of Comput, pp. 368–377. IEEE Computer Society Press, Sci (1991)
Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. IJGT 8, 109–113 (1979)
Gimbert, H.: Parity and Exploration Games on Infinite Graphs. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 56–70. Springer, Heidelberg (2004)
Grädel, E.: Positional Determinacy of Infinite Games. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 4–18. Springer, Heidelberg (2004)
Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games. Lecture Notes in Compter Science, vol. 2500. Springer, Heidelberg (2002)
Gimbert, H., Zielonka, W.: When can you play positionally? Proc. of MFCS ’04. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 686–697. Springer, Heidelberg (2004)
Zielonka, W., Gimbert, H.: Games Where You Can Play Optimally Without Any Memory. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 428–442. Springer, Heidelberg (2005)
Klarlund, N.: Progress measures, immediate determinacy, and a subset construction for tree automata. In: Proc. 7th IEEE Symp. on Logic in Computer Science (1992)
E. Kopczyński, Half-positional determinacy of infinite games. Draft. http://www.mimuw.edu.pl/~erykk/papers/hpwc.ps
Martin, D.A.: Borel determinacy. Ann. Math. 102, 363–371 (1975)
McNaughton, R.: Infinite games played on finite graphs. Annals of Pure and Applied Logic 65, 149–184 (1993)
Mostowski, A.W.: Games with forbidden positions. Technical Report 78, Uniwersytet Gdański, Instytut Matematyki (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kopczyński, E. (2006). Half-Positional Determinacy of Infinite Games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4052. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11787006_29
Download citation
DOI: https://doi.org/10.1007/11787006_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35907-4
Online ISBN: 978-3-540-35908-1
eBook Packages: Computer ScienceComputer Science (R0)