2026-07-24T03:16:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15826 2024-03-06T10:56:17Z ddc:004 open_access

Characterizing Omega-Regularity Through Finite-Memory Determinacy of Games on Infinite Graphs Bouyer, Patricia Randour, Mickael Vandenhove, Pierre two-player games on graphs infinite arenas finite-memory determinacy optimal strategies ω-regular languages We consider zero-sum games on infinite graphs, with objectives specified as sets of infinite words over some alphabet of colors. A well-studied class of objectives is the one of ω-regular objectives, due to its relation to many natural problems in theoretical computer science. We focus on the strategy complexity question: given an objective, how much memory does each player require to play as well as possible? A classical result is that finite-memory strategies suffice for both players when the objective is ω-regular. We show a reciprocal of that statement: when both players can play optimally with a chromatic finite-memory structure (i.e., whose updates can only observe colors) in all infinite game graphs, then the objective must be ω-regular. This provides a game-theoretic characterization of ω-regular objectives, and this characterization can help in obtaining memory bounds. Moreover, a by-product of our characterization is a new one-to-two-player lift: to show that chromatic finite-memory structures suffice to play optimally in two-player games on infinite graphs, it suffices to show it in the simpler case of one-player games on infinite graphs. We illustrate our results with the family of discounted-sum objectives, for which ω-regularity depends on the value of some parameters. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patricia Bouyer and Mickael Randour and Pierre Vandenhove 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.16 urn:nbn:de:0030-drops-158262 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode