Linear Time Algorithm for Weak Parity Games
| dc.creator | Chatterjee, Krishnendu | |
| dc.date | 2008-05-09 | |
| dc.date.accessioned | 2026-07-07T12:18:49Z | |
| dc.date.available | 2026-07-07T12:18:49Z | |
| dc.description | 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. | |
| dc.description | 7 pages, EECS UC Berkeley Technical Report | |
| dc.identifier | https://arxiv.org/abs/0805.1391 | |
| dc.identifier | http://arxiv.org/abs/0805.1391 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212543 | |
| dc.subject | Logic in Computer Science | |
| dc.title | Linear Time Algorithm for Weak Parity Games | |
| dc.type | text |