Thumbnail - No thumbnail

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

Type
Communication / Conférence
External document link
http://arxiv.org/abs/1102.3615v2
Date
2011
Conference title
9th International Symposium on Automated Technology for Verification and Analysis, ATVA 2011
Conference date
2011-10
Conference city
Taipei
Conference country
Taïwan
Book title
Automated Technology for Verification and Analysis 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011, Proceedings
Book author
Bultan, Tevfik; Hsiung, Pao-Ann
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
6996
Published in
Berlin
ISBN
978-3-642-24371-4
Number of pages
532
Pages
135-149
Publication identifier
Metadata
Show full item record
Author(s)
Bouyer, Patricia cc
Markey, Nicolas
Olschewski, Jörg
Ummels, Michael
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 / Keywords
permissiveness; mean-payoff parity games