2008/05/09 by Krishnendu Chatterjee, Chatterjee, Krishnendu · 1 citation
Computer Science · #Artificial Intelligence in Games #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.LO
paper · pdf · doi:10.48550/arxiv.0805.1391
7 pages, EECS UC Berkeley Technical Report
arxiv created 2008/05/09 · openalex publication_date 2008/05/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.