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

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

2011-02-17

arxiv.org/abs/1102.3615v2

Computer Science

Logic in Computer Science

30 pages, revised version

Scientific paper

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 the strategy. Using a translation into mean-payoff parity games, we prove that the problem of computing (the permissiveness of) a most permissive winning strategy is in NP intersected coNP. Along the way, we provide a new study of mean-payoff parity games. In particular, we prove that the opponent player has a memoryless optimal strategy and give a new algorithm for solving these games.

Affiliated with

Also associated with

No associations

Rating

Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-380779