Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Karoliina Lehtinen: A modal mu perspective on solving parity games in quasi-polynomial time

LFCS seminar: Karoliina Lehtinen: A modal mu perspective on solving parity games in quasi-polynomial time

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Jan 30, 2018
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

Parity games are infinite-duration games on finite graph, which arise at the intersection of logic, games and automata theory. The complexity of solving parity games -- i.e., deciding which player has a winning strategy --  is a long standing open problem. It is known to be quasi-polynomial in general, and polynomial for various restricted classes of parity games.

In this talk I present a modal mu account of the quasi-polynomial solvability of parity games, based on a new quasi-polynomial algorithm.

We will play a parameterised variation of parity games, called a k-register game, in which Player 0 has to produce a witness of her victory using a restricted amount of memory which depends on k. For every parity game there is a k such that solving the k-register game is equivalent to solving the parity game. We call this the register-index of a parity game and show that it is O(log n) in the size of the parity game.

This yields a quasi-polynomial algorithm for solving parity games, and a polynomial algorithm for solving games of bounded register-index. Showing that the descriptive complexity of parity games of register-index k depends on k, rather than on the number of priorities in the games then relates the quasi-polynomial solvability of parity games to complexity in the modal mu calculus.

 

Document Actions