Solving Odd-Fair Parity Games

This talk discusses the problem of efficiently solving parity games whereplayer Odd has to obey an additional strong transition fairness constraint onits vertices. We call such games Odd-fair Parity games. Banerjee et. al. showed that Odd-fair parity games can be solved via a fixed-point formula thathighly resembles the one for ‘regular’ parity games. In this talk, we presenta new a Zielonka-type algorithm for solving Odd-fair parity games, which notonly shares the same worst-case complexity as Zielonka’s algorithm for regularparity games but also preserves the algorithmic advantage that Zielonka’s algorithm possesses over other parity solvers with exponential time complexity, suchas Banerjee et. al. ’s fixed-point algorithm. Zielonka’s algorithm’s establishedreputation for solving parity games efficiently makes the Odd-fair Zielonka’s algorithm presented in this talk the best known generic algorithm to solve Odd-fairparity games. Contributed talk given by Irmak Saglam

Authors

• Irmak Saglam

Keywords

No keywords are indexed for this paper.