Infinite separation between general and chromatic memory. (English) Zbl 07857866
Soto, José A. (ed.) et al., Latin 2024: theoretical informatics. 16th Latin American symposium, Puerto Varas, Chile, March 18–22, 2024. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 14579, 114-128 (2024).
Summary: 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\).
For the entire collection see [Zbl 1539.68038].
For the entire collection see [Zbl 1539.68038].
MSC:
| 68Qxx | Theory of computing |
| 68Rxx | Discrete mathematics in relation to computer science |
| 68Wxx | Algorithms in computer science |
References:
| [1] | Bloem, R.; Chatterjee, K.; Jobstmann, B., Graph Games and Reactive Synthesis, Handbook of Model Checking, 921-962, 2018, Cham: Springer, Cham · Zbl 1392.68233 · doi:10.1007/978-3-319-10575-8_27 |
| [2] | Bouyer, P.; Randour, M.; Vandenhove, P., Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs, Theoretics, 2, 1-48, 2023 · Zbl 07875608 · doi:10.46298/theoretics.23.1 |
| [3] | 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) · Zbl 07471700 |
| [4] | Büchi, JR; Landweber, LH, Solving sequential conditions by finite-state strategies, Trans. Am. Math. Soc., 138, 295-311, 1969 · Zbl 0182.02302 · doi:10.1090/S0002-9947-1969-0280205-0 |
| [5] | 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, |
| [6] | 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) · Zbl 07830368 |
| [7] | 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) · Zbl 07870327 |
| [8] | 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) |
| [9] | 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) · Zbl 1360.68583 |
| [10] | 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) |
| [11] | Kopczyński, E.; Duparc, J.; Henzinger, TA, Omega-regular half-positional winning conditions, Computer Science Logic, 41-53, 2007, Heidelberg: Springer, Heidelberg · Zbl 1179.68071 · doi:10.1007/978-3-540-74915-8_7 |
| [12] | Kopczyński, E.: Half-positional determinacy of infinite games. PhD thesis, Warsaw University (2008) |
| [13] | Kozachinskiy, A.: State complexity of chromatic memory in infinite-duration games. arXiv preprint arXiv:2201.09297 (2022) |
| [14] | Le Roux, S.; Anselmo, M.; Della Vedova, G.; Manea, F.; Pauly, A., Time-aware uniformization of winning strategies, Beyond the Horizon of Computability, 193-204, 2020, Cham: Springer, Cham · Zbl 07633508 · doi:10.1007/978-3-030-51466-2_17 |
| [15] | Zielonka, W., Infinite games on finitely coloured graphs with applications to automata on infinite trees, Theoret. Comput. Sci., 200, 1-2, 135-183, 1998 · Zbl 0915.68120 · doi:10.1016/S0304-3975(98)00009-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
