Inproceedings: an article in a conference proceedings.
Solving Pushdown Games with a ∑3 Winning Condition
Title of the conference
Computer Science Logic : 11th Annual Conference of the EACSL Edinburgh, Scotland, UK, September 22–25, 2002 Proceedings
Lecture Notes in Computer Science
We study infinite two-player games over pushdown graphs with a winning condition that refers explicitly to the infinity of the game graph: A play is won by player 0 if some vertex is visited infinity often during the play. We show that the set of winning plays is a proper Sigma(3)-set in the Borel hierarchy, thus transcending the Boolean closure of Sigma(2)-sets which arises with the standard automata theoretic winning conditions (such as the Muller, Rabin, or parity condition). We also show that this Sigma(3)-game over pushdown graphs can be solved effectively (by a computation of the winning region of player 0 and his memoryless winning strategy). This seems to be a first example of an effectively solvable game beyond the second level of the Borel hierarchy.
Web of science
Last modification date