Abstract
In this paper, we construct a winning condition W over a finite set of colors such that, first, every finite arena has a strategy with 2 states of general memory which is optimal w.r.t. W, and second, there exists no k such that every finite arena has a strategy with k states of chromatic memory which is optimal w.r.t. W.
The author is funded by ANID - Millennium Science Initiative Program - Code ICN17002, and the National Center for Artificial Intelligence CENIA FB210017, Basal ANID.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
There are papers that study these games over infinite graphs, but in this note we only work with finite graphs.
- 2.
In their original definition, the “memory structure” (see Preliminaries) must be the same in all arenas. When C is finite, this definition is equivalent, because there are just finitely many chromatic memory structures up to a certain size. If none of them works for all arenas, one can construct a finite arena where none of them works.
- 3.
We do not have to redefine S for every starting position. The same S can be played from any of them.
References
Bloem, R., Chatterjee, K., Jobstmann, B.: Graph Games and Reactive Synthesis. In: Handbook of Model Checking, pp. 921–962. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-10575-8_27
Bouyer, P., Randour, M., Vandenhove, P.: Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs. Theoretics 2, 1–48 (2023)
Bouyer, P., Le Roux, S., Oualhadj, Y., Randour, M., Vandenhove, P.: Games where you can play optimally with arena-independent finite memory. Logical Methods Comput. Sci. 18.11:1–11:44 (2022)
Büchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Trans. Am. Math. Soc. 138, 295–311 (1969)
Bouyer, P., Fijalkow, N., Randour, M., and Vandenhove, P.: How to play optimally for regular objectives? In: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 261, pp. 118:1–118:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
Casares, A.: On the minimisation of transition-based rabin automata and the chromatic memory requirements of muller conditions. In: Manea, F., Simpson, A. (eds.) 30th Eacsl Annual Conference on Computer Science Logic (CSL 2022), Dagstuhl, Germany. Leibniz International Proceedings in Informatics (LIPIcs), vol. 216, pp. 12:1–12:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
Casares, A., Colcombet, T., Lehtinen, K.: On the size of good-for-games Rabin automata and its link with the memory in Muller games. In: 349th International Colloquium on Automata, Languages, and Programming (ICALP ). Leibniz International Proceedings in Informatics (LIPIcs), vol. 229, pp. 117:1–117:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Generalized mean-payoff and energy games. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2010)
Colcombet, T., Fijalkow, N., Horn, F.: Playing safe. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2014)
Dziembowski, S., Jurdzinski, M., Walukiewicz, I.: How much memory is needed to win infinite games? In: Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science, pp. 99–110. IEEE (1997)
Kopczyński, E.: Omega-regular half-positional winning conditions. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646, pp. 41–53. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74915-8_7
Kopczyński, E.: Half-positional determinacy of infinite games. PhD thesis, Warsaw University (2008)
Kozachinskiy, A.: State complexity of chromatic memory in infinite-duration games. arXiv preprint arXiv:2201.09297 (2022)
Le Roux, S.: Time-aware uniformization of winning strategies. In: Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (eds.) CiE 2020. LNCS, vol. 12098, pp. 193–204. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51466-2_17
Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoret. Comput. Sci. 200(1–2), 135–183 (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kozachinskiy, A. (2024). Infinite Separation Between General and Chromatic Memory. In: Soto, J.A., Wiese, A. (eds) LATIN 2024: Theoretical Informatics. LATIN 2024. Lecture Notes in Computer Science, vol 14579. Springer, Cham. https://doi.org/10.1007/978-3-031-55601-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-55601-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-55600-5
Online ISBN: 978-3-031-55601-2
eBook Packages: Computer ScienceComputer Science (R0)