The theory of universal graphs for infinite duration games

Speaker(s)

Nathanaël Fijalkow

Affiliation

LaBRI

Date

April 28, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---