10.4230/LIPICS.FSTTCS.2008.1768
Graedel, Erich
Erich
Graedel
Banach-Mazur Games on Graphs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Games
strategies
determinacy
positional determinacy
definability
complexity
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17684
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
15
364
382
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
19 pages
465771 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We survey determinacy, definability, and
complexity issues of Banach-Mazur games on finite and
infinite graphs.
Infinite games where two players take turns to move a token
through a directed graph, thus tracing out an infinite path,
have numerous applications in different branches of mathematics
and computer science. In the usual format,
the possible moves of the players are given by
the edges of the graph; in each move
a player takes the token from its current position
along an edge to a next position. In Banach-Mazur games
the players instead select in each move a \emph{path}
of arbitrary finite length rather than just an edge.
In both cases the outcome of a play is an infinite
path. A winning condition is thus given by a set of
infinite paths which is often specified by a logical formula,
for instance from S1S, LTL, or first-order logic.
Banach-Mazur games have a long tradition in descriptive
set theory and topology, and they have recently been shown to
have interesting applications also in computer science,
for instance for planning in nondeterministic domains,
for the study of fairness in concurrent systems, and
for the semantics of timed automata.
It turns out that Banach-Mazur games behave quite differently than
the usual graph games. Often they admit simpler winning strategies
and more efficient algorithmic solutions. For instance, Banach-Mazur
games with $\omega$-regular winning conditions always have
positional winning strategies, and winning positions
for finite Banach-Mazur games with Muller winning condition
are computable in polynomial time.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 364-382