## Author: Karoliina Lehtinen

## Paper Information

Title: | A modal mu perspective on solving parity games in quasipolynomial time. |

Authors: | Karoliina Lehtinen |

Proceedings: | LICS PDF files |

Editors: | Anuj Dawar and Erich Grädel |

Keywords: | parity games, algorithmic complexity, descriptive complexity, modal mu |

Abstract: | ABSTRACT. We present a new quasi-polynomial algorithm for solving parity games. It is based on a new bisimulation invariant measure of complexity for parity games, called the register-index, which captures the complexity of the priority assignment. For fixed parameter k, the class of games with register-index bounded by k is solvable in polynomial time. We show that the register-index of parity games of size n is bounded by O(log n) and derive a quasi-polynomial algorithm. Finally we give the first descriptive complexity account of the quasi-polynomial solvability of parity games: The winning regions of parity games with p priorities and register-index k are described by a modal μ formula of which the complexity, as measured by its alternation depth, depends on k rather than p. |

Pages: | 10 |

Talk: | Jul 09 14:00 (Session 49D) |

Paper: |