Solving Pushdown Games with a ∑3 Winning Condition

Détails

ID Serval
serval:BIB_061B51BC8C9E
Type
Actes de conférence (partie): contribution originale à la littérature scientifique, publiée à l'occasion de conférences scientifiques, dans un ouvrage de compte-rendu (proceedings), ou dans l'édition spéciale d'un journal reconnu (conference proceedings).
Collection
Publications
Titre
Solving Pushdown Games with a ∑3 Winning Condition
Titre de la conférence
Computer Science Logic : 11th Annual Conference of the EACSL Edinburgh, Scotland, UK, September 22–25, 2002 Proceedings
Auteur⸱e⸱s
Cachat T., Duparc J., Thomas W.
Editeur
Springer
ISBN
978-3-540-44240-0
978-3-540-45793-0
Statut éditorial
Publié
Date de publication
2002
Peer-reviewed
Oui
Editeur⸱rice scientifique
Bradfield J.
Volume
2471
Série
Lecture Notes in Computer Science
Pages
322-336
Langue
anglais
Résumé
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
Création de la notice
23/01/2008 19:20
Dernière modification de la notice
20/08/2019 12:28
Données d'usage