Linear Time Algorithm for Weak Parity Games

Details Linear Time Algorithm for Weak Parity Games Linear Time Algorithm for Weak Parity Games

2008-05-09

arxiv.org/abs/0805.1391v1

Computer Science

Logic in Computer Science

7 pages, EECS UC Berkeley Technical Report

Scientific paper

We consider games played on graphs with the winning conditions for the players specified as weak-parity conditions. In weak-parity conditions the winner of a play is decided by looking into the set of states appearing in the play, rather than the set of states appearing infinitely often in the play. A naive analysis of the classical algorithm for weak-parity games yields a quadratic time algorithm. We present a linear time algorithm for solving weak-parity games.

Affiliated with

Also associated with

No associations

Rating

Linear Time Algorithm for Weak Parity Games 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 Linear Time Algorithm for Weak Parity Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Time Algorithm for Weak Parity Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-332715