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érenceExternal document link
http://arxiv.org/abs/1102.3615v2Date
2011Conference title
9th International Symposium on Automated Technology for Verification and Analysis, ATVA 2011Conference date
2011-10Conference city
TaipeiConference country
TaïwanBook title
Automated Technology for Verification and Analysis 9th International Symposium, ATVA 2011, Taipei, Taiwan, October 11-14, 2011, ProceedingsBook author
Bultan, Tevfik; Hsiung, Pao-AnnPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
6996Published in
Berlin
ISBN
978-3-642-24371-4
Number of pages
532Pages
135-149
Publication identifier
Metadata
Show full item recordAbstract (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 gamesRelated items
Showing items related by title and author.
-
Bel Mokadem, Houda; Bérard, Béatrice; Bouyer, Patricia; Laroussinie, François (2005) Communication / Conférence
-
Gajarsky, Jakub; Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Ordyniak, Sebastian (2015) Communication / Conférence
-
Hanaka, Tesshu; Lampis, Michael (2022) Communication / Conférence
-
Renault, Jérôme; Ziliotto, Bruno (2020) Article accepté pour publication ou publié
-
Oliu-Barton, Miquel; Ziliotto, Bruno (2018) Document de travail / Working paper