On the positional determinacy of edge-labeled games
type: Item
instance of: scholarly article
title: On the positional determinacy of edge-labeled games
zbMATH Open document ID: 1138.91015
author: Thomas Colcombet
author: Damian Niwiński
published in: Theoretical Computer Science
publication date: 2006-03-24T00:00:00Z
review text: The authors consider games with perfect information of possibly infinite duration played by two players. The mathematical structure used is a graph whose vertices are positions and edges specify possible moves. In the literature it is known that parity games admit positional determinacy: For any position one of the players can win the game using a positional strategy. This property holds if edges rather than vertices are labeled. In this paper it is shown that in this latter case the converse is also true.
reviewed by: Massimiliano Ferrara
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5015098
zbMATH Keywords: parity games
zbMATH Keywords: positional determinacy
zbMATH Keywords: winning condition
MaRDI profile type: Publication
full work available at URL: j.tcs.2005.10.046
OpenAlex ID: W1993569943
cites work: Positional strategies for mean payoff games
cites work: Borel determinacy
cites work: Infinite games played on finite graphs
cites work: Q4369409
cites work: Stochastic Games
cites work: Pushdown processes: Games and model-checking
cites work: Infinite games on finitely coloured graphs with applications to automata on infinite trees
cites work: STACS 2004
DOI: 10.1016/J.TCS.2005.10.046
description: scientific article; zbMATH DE number 5015098