A correspondence between memory and automata for Muller languages

Speaker(s)

Antonio Casares Santos

Affiliation

LaBRI, Université de Bordeaux

Date

Dec. 14, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

In this talk, we will be interested in infinite-duration games using Muller winning conditions, that is, the objective of such games is given by a boolean combination of colors that have to appear infinitely often. In Muller games, finite memory strategies suffice, meaning that Eve can play optimally by using strategies implemented by finite automata processing the moves played in the game. I will present the following characterization: -Memory structures that can keep track of paths in the game graph correspond to Good-For-Games Rabin automata. -Memory structures that can only keep track of the colors produced in the game correspond to deterministic Rabin automata. I will also show that there is an exponential gap in the size of the two models of automata. For this, I will present a novel technique granting lower bounds for deterministic Rabin automata.

---