A short proof of correctness of the quasi-polynomial time algorithm for parity games

2017/02/07 by Hugo Gimbert, Gimbert, Hugo, Rasmus Ibsen-Jensen +1
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #cs.GT

paper · pdf · doi:10.48550/arxiv.1702.01953

arxiv created 2017/04/24 · arxiv updated 2017/04/25

Abstract

Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm.

Related

• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space
• Parity Games: Another View on Lehtinen's Algorithm
• Deciding Parity Games in Quasi-polynomial Time
• Improving the complexity of Parys' recursive algorithm