Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited

被引：0
作者：
Bouyer, Patricia [1 ]
Markey, Nicolas [1 ]
Olschewski, Joerg
Ummels, Michael [1 ]
机构：
[1] CNRS, LSV, F-75700 Paris, France
来源：
AUTOMATED TECHNOLOGY FOR VERIFICATION AND ANALYSIS | 2011年 / 6996卷
关键词：
INFINITE GAMES; DETERMINACY; AUTOMATA; GRAPHS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We study nondeterministic strategies in parity games with the aim of computing a most permissive winning strategy. Following earlier work, we measure permissiveness in terms of the average number/weight of transitions blocked by a strategy. Using a translation into mean-payoff parity games, we prove that deciding (the permissiveness of) a most permissive winning strategy is in NP boolean AND coNP. Along the way, we provide a new study of mean-payoff parity games. In particular, we give a new algorithm for solving these games, which beats all previously known algorithms for this problem.
引用
收藏
页码：135 / +
页数：3
相关论文
共 22 条
[1]  
[Anonymous], 1991, Proc. 32nd IEEE Symp. Found, DOI DOI 10.1109/SFCS.1991.185392
[2]   Permissive strategies: From parity games to safety games [J].
Bernet, J ;
Janin, D ;
Walukiewicz, I .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2002, 36 (03) :261-275
[3]  
Bouyer P., 2011, LSV1117 ENS CACH
[4]  
Bouyer P, 2008, LECT NOTES COMPUT SC, V5215, P33, DOI 10.1007/978-3-540-85778-5_4
[5]  
Bouyer P, 2009, LECT NOTES COMPUT SC, V5710, P196, DOI 10.1007/978-3-642-04081-8_14
[6]  
Chakrabarti A, 2003, LECT NOTES COMPUT SC, V2855, P117
[7]  
Chatterjee K, 2005, IEEE S LOG, P178
[8]  
Chatterjee K, 2007, LECT NOTES COMPUT SC, V4423, P153
[9]   Generalized Mean-payoff and Energy Games [J].
Chatterjee, Krishnendu ;
Doyen, Laurent ;
Henzinger, Thomas A. ;
Raskin, Jean-Francois .
IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010), 2010, 8 :505-516
[10]  
Chatterjee K, 2010, LECT NOTES COMPUT SC, V6199, P599, DOI 10.1007/978-3-642-14162-1_50
123