Discrete mathematics and logic : between mathematics and the computer science / Les mathématiques discrètes et la logique: des mathématiques à l'informatique

Collection Discrete mathematics and logic : between mathematics and the computer science / Les mathématiques discrètes et la logique: des mathématiques à l'informatique

Organisateur(s) Dzamonja, Mirna ; Schmitz, Sylvain ; Schnoebelen, Philippe ; Vaananen, Jouko

Date(s) 16/01/2023 - 20/01/2023

URL associée https://conferences.cirm-math.fr/2758.html

00:00:00 / 00:00:00

4 4

The true colors of memory: a tour of chromatic-memory strategies in zero-sum games on graphs

De Patricia Bouyer

Two-player turn-based zero-sum games on (finite or infinite) graphs are a central framework in theoretical computer science — notably as a tool for controller synthesis, but also due to their connection with logic and automata theory. A crucial challenge in the field is to understand how complex strategies need to be to play optimally, given a type of game and a winning objective. I will give a tour of recent advances aiming to characterize games where finite-memory strategies suffice (i.e., using a limited amount of information about the past). We mostly focus on so-called chromatic memory, which is limited to using colors — the basic building blocks of objectives — seen along a play to update itself. Chromatic memory has the advantage of being usable in different game graphs, and the corresponding class of strategies turns out to be of great interest to both the practical and the theoretical sides.

Informations sur la vidéo

Date de captation 16/01/2023
Date de publication 13/02/2023
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Audience Chercheurs, Doctorants
Réalisateur(s) Jean Petit
Format MP4

Données de citation

DOI 10.24350/CIRM.V.19994103
Citer cette vidéo Bouyer, Patricia (16/01/2023). The true colors of memory: a tour of chromatic-memory strategies in zero-sum games on graphs. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19994103
URL https://dx.doi.org/10.24350/CIRM.V.19994103

Domaine(s)

Informatique et théorie des jeux

Bibliographie

BOUYER, Patricia, RANDOUR, Mickael, et VANDENHOVE, Pierre. The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs (Invited Talk). In : 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. - https://drops.dagstuhl.de/opus/volltexte/2022/17395/

Codes MSC

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Toutes les vidéos de la collection

01:05:56

publiée le 13 février 2023

Algebra vs Logic over (generalised) words

De Thomas Colcombet

01:04:38

publiée le 13 février 2023

Categoricity of atomic classes in small cardinals, in ZFC

De Saharon Shelah

01:01:13

publiée le 13 février 2023

A quick and partial survey on the complexity of query answering

De Arnaud Durand

01:02:56

publiée le 13 février 2023

The true colors of memory: a tour of chromatic-memory strategies in zero-sum games on graphs

De Patricia Bouyer

Copyright Carmin.tv 2024

Donner son avis