Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs
TheoretiCS · 2023
DOI: 10.46298/theoretics.23.1 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von Patricia Bouyer und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref).
Abstract (Originalsprache)
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 $\omega$-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 $\omega$-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 $\omega$-regular. This provides a game-theoretic characterization of $\omega$-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 $\omega$-regularity depends on the value of some parameters.
Zitieren
APA
Bouyer, P., Randour, M., & Vandenhove, P. (2023). Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs. TheoretiCS. https://doi.org/10.46298/theoretics.23.1
Vancouver
Bouyer P, Randour M, Vandenhove P. Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs. TheoretiCS. 2023. doi:10.46298/theoretics.23.1
BibTeX
@article{Bouyer2023,
author = {Bouyer, Patricia and Randour, Mickael and Vandenhove, Pierre},
title = {Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs},
journal = {TheoretiCS},
year = {2023},
doi = {10.46298/theoretics.23.1}
}
EUVIMED