Výsledky vyhledávání - "Finite-Memory determinacy"

Complexité des stratégies des jeux sur graphes à somme nulle

Autor: Vandenhove, Pierre

Publikováno v: Computer Science and Game Theory [cs.GT]. Université Paris-Saclay; Université de Mons, 2023. English. ⟨NNT : 2023UPASG029⟩

We study two-player zero-sum turn-based games on graphs, a framework of choice in theoretical computer science. Such games model the possibly infinite interaction between a computer system (often called reactive) and its environment. The system, seen

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______165::96702db02b773a738d4bdcf41a54bcfd
https://theses.hal.science/tel-04095220

Zobrazit plný text záznamu

Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs

Autor: Bouyer, Patricia, Randour, Mickael, Vandenhove, Pierre

Publikováno v: STACS'22
STACS'22, Mar 2022, Online, France. ⟨10.4230/LIPIcs.STACS.2022.16⟩

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 problem

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::33b16948c417ec29c73a391f19750f8b
https://doi.org/10.46298/theoretics.23.1

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Games Where You Can Play Optimally with Arena-Independent Finite Memory

Autor: Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, Pierre Vandenhove

Publikováno v: Logical Methods in Computer Science
Logical Methods in Computer Science, 2022, Volume 18, Issue 1, ⟨10.46298/lmcs-18(1:11)2022⟩
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022, Volume 18, Issue 1, ⟨10.46298/lmcs-18(1:11)2022⟩
31st International Conference on Concurrency Theory (CONCUR'20)
31st International Conference on Concurrency Theory (CONCUR'20), Sep 2020, Vienna, Austria. ⟨10.4230/LIPIcs.CONCUR.2020.18⟩

Updated title, full version of CONCUR 2020 conference paper; International audience; For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::246c21d3bf3da52080cb0e16729c29ff
https://doi.org/10.46298/lmcs-18(1:11)2022

Zobrazit plný text záznamu

One-To-Two-Player Lifting for Mildly Growing Memory

Autor: Kozachinskiy, Alexander

We investigate a phenomenon of "one-to-two-player lifting" in infinite-duration two-player games on graphs with zero-sum objectives. More specifically, let �� be a class of strategies. It turns out that in many cases, to show that all two-p

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::062d151d651fd4e8060ae8d7d3cad975

Zobrazit plný text záznamu

Arena-Independent Finite-Memory Determinacy in Stochastic Games

Autor: Bouyer, Patricia, Oualhadj, Youssouf, Randour, Mickael, Vandenhove, Pierre

Publikováno v: CONCUR'21
CONCUR'21, Aug 2021, Paris, France. ⟨10.4230/LIPIcs.CONCUR.2021.26⟩

We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, an important question is the one of strategy complexity: what kinds of

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::16814c83a34036d7d66810b782591193
https://hal.science/hal-03240080

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání