Positive Games and persistent Strategies

Details

Serval ID
serval:BIB_3349B31ACDD7
Type
Inproceedings: an article in a conference proceedings.
Collection
Publications
Institution
Title
Positive Games and persistent Strategies
Title of the conference
12th Annual Conference of the European Association for Computer Science Logic
Author(s)
Duparc J.
Publisher
Springer
Address
Vienna, Austria
ISBN
978-3-540-40801-7
978-3-540-45220-1
Publication state
Published
Issued date
2003
Peer-reviewed
Oui
Volume
2803
Series
Lecture Notes in Computer Science
Pages
183-196
Language
english
Abstract
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
Create date
19/11/2007 10:04
Last modification date
20/08/2019 13:19
Usage data