Positive Games and persistent Strategies

Détails

ID Serval
serval:BIB_3349B31ACDD7
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
Institution
Titre
Positive Games and persistent Strategies
Titre de la conférence
12th Annual Conference of the European Association for Computer Science Logic
Auteur⸱e⸱s
Duparc J.
Editeur
Springer
Adresse
Vienna, Austria
ISBN
978-3-540-40801-7
978-3-540-45220-1
Statut éditorial
Publié
Date de publication
2003
Peer-reviewed
Oui
Volume
2803
Série
Lecture Notes in Computer Science
Pages
183-196
Langue
anglais
Résumé
At CSL 2002, Jerzy Marcinkowsi and Tomasz Truderung presented the notions of positive games and persistent strategies [8]. A strategy is persistent if, given any finite or infinite run played on a game graph, each time the player visits some vertex already encountered, this player repeats the decision made when visiting this vertex for the first time. Such strategies require memory, but once a choice is made, it is made for ever. So, persistent strategies are a weakening of memoryless strategies.
The same authors established a direct relation between positive games and the existence of persistent winning strategies. We give a description of such games by means of their topological complexity. In games played on finite graphs, positive games are unexpectedly simple. On the contrary, infinite game graphs, as well as infinite alphabets, yield positive sets involved in non determined games.
Last, we discuss positive Muller winning conditions. Although they do not help to discriminate between memoryless and LAR winning strategies, they bear a strong topological characterization.
Web of science
Création de la notice
19/11/2007 10:04
Dernière modification de la notice
20/08/2019 13:19
Données d'usage