Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited
Bouyer, Patricia; Markey, Nicolas; Olschewski, Jörg; Ummels, Michael (2011), Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited, in Bultan, Tevfik; Hsiung, Pao-Ann, Automated Technology for Verification and Analysis 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011, Proceedings, Springer : Berlin, p. 135-149. http://dx.doi.org/10.1007/978-3-642-24372-1_11
TypeCommunication / Conférence
External document linkhttp://arxiv.org/abs/1102.3615v2
Conference title9th International Symposium on Automated Technology for Verification and Analysis, ATVA 2011
Book titleAutomated Technology for Verification and Analysis 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011, Proceedings
Book authorBultan, Tevfik; Hsiung, Pao-Ann
Series titleLecture Notes in Computer Science
Number of pages532
MetadataShow full item record
Abstract (EN)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∩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.
Subjects / Keywordspermissiveness; mean-payoff parity games
Showing items related by title and author.