パリティゲーム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/16 06:46 UTC 版)
パリティゲーム (parity games) は彩色された有向グラフ上でプレイされる理論上のゲームである。各ノードは優先度と呼ばれる(通常は有限種類の)自然数で彩色されている。このゲームはプレイヤー0とプレイヤー1の二名によってプレイされる。各プレイヤーは、ゲーム上に一個だけある駒をグラフの辺にそって動かす。手番は、その駒の現在地によって決められている。この操作を繰り返し(場合によっては無限回)行うことにより、プレイと呼ばれるパスが定まる。
- ^ D. A. Martin: Borel determinacy, The Annals of Mathematics, Vol 102 No. 2 pp. 363–371 (1975)
- ^ Rabin, MO (1969). “Decidability of second-order theories and automata on infinite trees”. Transactions of the American Mathematical Society (American Mathematical Society) 141: 1–35. doi:10.2307/1995086. JSTOR 1995086.
- ^ E. A. Emerson and C. S. Jutla: Tree Automata, Mu-Calculus and Determinacy, IEEE Proc. Foundations of Computer Science, pp 368–377 (1991), ISBN 0-8186-2445-0
- ^ A. Mostowski: Games with forbidden positions, University of Gdansk, Tech. Report 78 (1991)
- ^ Zielonka, W (1998). “Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees”. Theor. Comput. Sci. 200 (1–2): 135–183. doi:10.1016/S0304-3975(98)00009-7.
- ^ Marcin Jurdziński (1998), “Deciding the winner in parity games is in UP∩ co-UP”, Information Processing Letters (Elsevier) 68 (3): 119-124
- ^ Calude, Cristian S and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank, “Deciding parity games in quasipolynomial time”, STOC 2017
[続きの解説]
「パリティゲーム」の続きの解説一覧
- 1 パリティゲームとは
- 2 パリティゲームの概要
- 3 関連するゲームとそれらの決定問題
- 4 外部リンク
- パリティゲームのページへのリンク
