Games with winning conditions of high Borel complexity
type: Item
instance of: scholarly article
title: Games with winning conditions of high Borel complexity
zbMATH Open document ID: 1125.91024
author: Olivier Serre
published in: Theoretical Computer Science
publication date: 2006-03-20T00:00:00Z
review text: This research work represents a significant contribution to the study of the infinite two-player games on pushdown graphs. The author establishes the best recent result concerning the families of decidable winning conditions for arbitrary finite Borel complexity with the important particular cases of games played on finite graphs. The method provides effective winning strategies and the exact form of the winning sets together with the existence of positional strategies remains open. Several pertinent references complete the paper.
reviewed by: Vasile Postolică
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 91A05
zbMATH DE Number: 5013344
zbMATH Keywords: pushdown automata
zbMATH Keywords: infinite two player games
zbMATH Keywords: winning decidable condition
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.10.024
OpenAlex ID: W2073412815
cites work: Games for synthesis of controllers with partial observation.
cites work: FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
cites work: Uniform solution of parity games on prefix-recognizable graphs
cites work: Q4411832
cites work: \(\omega\)-computations on deterministic pushdown machines
cites work: Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
cites work: On model checking for the \(\mu\)-calculus and its fragments
cites work: Topological properties of omega context-free languages
cites work: Computer Science Logic
cites work: Q4501540
cites work: Topology and descriptive set theory
cites work: Q2754072
cites work: Q4411828
cites work: Borel determinacy
cites work: Q3221403
cites work: Q5317419
cites work: Note on winning positions on pushdown games with \(\omega\)-regular conditions
cites work: On the synthesis of strategies in infinite games
cites work: Q2754084
cites work: Pushdown processes: Games and model-checking
cites work: Infinite games on finitely coloured graphs with applications to automata on infinite trees
DOI: 10.1016/J.TCS.2005.10.024
Recommended article: Automata, Languages and Programming
Recommended article: Q5472876
Recommended article: Mathematical Foundations of Computer Science 2005
Recommended article: Q3973044
Recommended article: Game-theoretical aspects of the Borel conjecture
Recommended article: Borel Games and the Baire Property
Recommended article: Complexities of winning strategies in diophantine games
Recommended article: On the complexity of problems on simple games
Recommended article: Algorithms – ESA 2005
Recommended article: Determinateness of certain almost-Borel games
description: scientific article; zbMATH DE number 5013344