On the positional determinacy of edge-labeled games

被引：12

作者：

Colcombet, T

Niwinski, D

机构：

[1] Institute of Informatics, Warsaw University

来源：

THEORETICAL COMPUTER SCIENCE | 2006年 / 352卷 / 1-3期

关键词：

parity games; positional detenninacy; winning condition;

D O I：

10.1016/j.tcs.2005.10.046

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is well known that games with the parity winning condition admit positional determinacy: the winner has always a positional (memoryless) strategy. This property continues to hold if edges rather than vertices are labeled. We show that in this latter case the converse is also true. That is, a winning condition over arbitrary set of colors admits positional determinacy in all games if and only if it can be reduced to a parity condition with some finite number of priorities. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：190 / 196

页数：7

共 11 条

[1] Ehrenfeucht A., 1979, International Journal of Game Theory, V8, P109, DOI 10.1007/BF01768705
[2] EMERSON EA, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P368, DOI 10.1109/SFCS.1991.185392
[3] GRADEL E, 2004, P STACS 04
[4] GRADEL I, 2004, UNPUB POSITIONAL DET
[5] BOREL DETERMINACY
MARTIN, DA
[J]. ANNALS OF MATHEMATICS, 1975, 102 (02) : 363 - 371
[6] INFINITE GAMES PLAYED ON FINITE GRAPHS
MCNAUGHTON, R
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1993, 65 (02) : 149 - 184
[7] Mostowski A., 1991, GAMES FORBIDDEN POSI
[8] Mycielski Jan, 1992, Handbook of Game Theory with Economic Application, P41, DOI 10.1016/S1574-0005(05)80006-2
[9] STOCHASTIC GAMES
SHAPLEY, LS
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1953, 39 (10) : 1095 - 1100
[10] Pushdown processes: Games and model-checking
Walukiewicz, I
[J]. INFORMATION AND COMPUTATION, 2001, 164 (02) : 234 - 263

← 1 2 →