Solving Pushdown Games with a ∑3 Winning Condition
Details
Serval ID
serval:BIB_061B51BC8C9E
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
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
Publisher
Springer
ISBN
978-3-540-44240-0
978-3-540-45793-0
978-3-540-45793-0
Publication state
Published
Issued date
2002
Peer-reviewed
Oui
Editor
Bradfield J.
Volume
2471
Series
Lecture Notes in Computer Science
Pages
322-336
Language
english
Abstract
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
Create date
23/01/2008 19:20
Last modification date
20/08/2019 12:28