DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2022-03-09 - Colloque/Article dans les actes avec comité de lecture - Anglais - 16 page(s)

Bouyer Patricia, Randour Mickaël , Vandenhove Pierre , "Characterizing Omega-Regularity Through Finite-Memory Determinacy of Games on Infinite Graphs" in Symposium on Theoretical Aspects of Computer Science, Marseille, France, 2022

  • Codes CREF : Logique mathématique (DI1170), Théorie des algorithmes (DI1164), Informatique mathématique (DI1160), Informatique générale (DI1162), Théorie de la décision et des jeux (DI1134)
  • Unités de recherche UMONS : Mathématiques effectives (S820)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)
Texte intégral :

Abstract(s) :

(Anglais) 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.