The theory of universal graphs for infinite duration games

Prelegent(ci)

Nathanaël Fijalkow

Afiliacja

LaBRI

Termin

28 kwietnia 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

2017 was a special year in the world of parity games. Now that the dust has settled, what have we learned from the new quasi polynomial algorithms? In this talk I'll introduce the notion of universal graphs, and argue the following: - they give nice generic (value iteration) algorithms for any positionally determined objective - they capture (some of) the combinatorial contents behind the different algorithms for parity games - maybe more importantly, they are useful beyond parity games! I'll describe applications to other objectives: mean payoff, disjunctions of mean payoff, disjunctions of parity and mean payoff, and Rabin. In each case the algorithms achieve or improve the state of the art complexity for solving these games. Joint work with Thomas Colcombet, Pierre Ohlmann, Paweł Gawrychowski, and ongoing work with Antonio Casares.

---