RECURSIVE ALGORITHM FOR PARITY GAMES REQUIRES EXPONENTIAL TIME

作     者：Friedmann, Oliver 

作者机构：LMU Munchen Inst Informat D-80538 Munich Germany 

出 版 物：《RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS》 (法国自动化、信息与运筹学；理论与应用信息)

年 卷 期：2011年第45卷第4期

页      面：449-457页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parity games recursive algorithm lower bound mu calculus model checking 

摘      要：This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.