Parity game
http://dbpedia.org/resource/Parity_game
En informatique théorique, un jeu de parité est un jeu à deux joueurs sur un graphe orienté où chaque sommet est étiqueté par un entier, appelé couleur ou priorité. Chaque joueur possède son propre sous-ensemble de sommets. Une partie est un chemin infini dans le graphe. Le premier joueur gagne lorsque la plus grande couleur visitée une infinité de fois est paire (chez certains auteurs, c'est lorsque la plus petite couleur visitée une infinité de fois est paire/impaire ; ces variantes sont fondamentalement équivalentes). Les jeux de parité sont importants en vérification de modèles, en particulier lorsque la propriété temporelle est exprimée en mu-calcul.
rdf:langString
Ein Paritätsspiel ist ein unendliches Spiel mit perfekter Information zwischen zwei Spielern auf einem gerichteten Graphen. Die Knoten des Graphen sind zwischen den Spielern aufgeteilt, so dass jeder Spieler für seine Knoten entscheiden kann, wie von diesen weitergezogen werden soll. Außerdem ist jedem Knoten als Priorität (manchmal auch Farbe genannt) eine natürliche Zahl zugeordnet.
rdf:langString
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owner of the node that the token falls on selects the successor node, resulting in a (possibly infinite) path, called the play. Parity games lie in the third level of the Borel hierarchy, and are consequently determined.
rdf:langString
Gry parzystości – gry pomiędzy dwoma graczami, toczone na skierowanym grafie etykietowanym gdzie to zbiór wierzchołków grafu, a to zbiór jego krawędzi. Potencjalnie zbiór może być nieskończony. Gracze są z angielskiego nazywani Odd i Even. Każdy wierzchołek jest wierzchołkiem jednego z graczy, to znaczy to ten gracz wykonuje z niego ruch. Dana jest funkcja która każdemu wierzchołkowi przypisuje nieujemną liczbę całkowitą zwaną rankiem. Zakłada się, że obraz funkcji jest skończony. Gra polega na tym, że gracze wykonują ruchy (zgodne z krawędziami ze zbioru ) na grafie gry, w danym momencie rusza się ten, który jest właścicielem danego wierzchołka. Jeśli w pewnym momencie któryś z graczy nie może wykonać ruchu, to przegrywa, natomiast jeśli gra toczy się w nieskończoność, to przygląda
rdf:langString
パリティゲーム (parity games) は彩色された有向グラフ上でプレイされる理論上のゲームである。各ノードは優先度と呼ばれる(通常は有限種類の)自然数で彩色されている。このゲームはプレイヤー0とプレイヤー1の二名によってプレイされる。各プレイヤーは、ゲーム上に一個だけある駒をグラフの辺にそって動かす。手番は、その駒の現在地によって決められている。この操作を繰り返し(場合によっては無限回)行うことにより、プレイと呼ばれるパスが定まる。 有限長のプレイの場合、駒を動かせなくなったプレイヤーが敗者で、敗者でない側が勝者となる。無限長のプレイの勝者は、プレイ中に現れる優先度の値によって決定される。プレイ中に無限回現れた優先度のうち、最大の値が偶数ならばプレイヤー0の勝利、奇数ならばプレイヤー1の勝利となる。(偶奇が逆だったり、最大値のかわりに最小値を使う場合もある。) この偶奇性が「パリティ」の由来であろう。 パリティゲームはの3層目に属する。したがってパリティゲームは決定的である。 n後者演算に関する二階の理論の決定可能性に関するラビンの証明では、パリティゲームに類似のゲームが暗黙的に使われ、該当ゲームの決定性も証明されている。 を使えば、パリティゲームの決定性に対するより単純な証明を与えることもできる。
rdf:langString
rdf:langString
Paritätsspiel
rdf:langString
Jeu de parité
rdf:langString
パリティゲーム
rdf:langString
Parity game
rdf:langString
Gra parzystości
xsd:integer
7624304
xsd:integer
1121935613
rdf:langString
Ein Paritätsspiel ist ein unendliches Spiel mit perfekter Information zwischen zwei Spielern auf einem gerichteten Graphen. Die Knoten des Graphen sind zwischen den Spielern aufgeteilt, so dass jeder Spieler für seine Knoten entscheiden kann, wie von diesen weitergezogen werden soll. Außerdem ist jedem Knoten als Priorität (manchmal auch Farbe genannt) eine natürliche Zahl zugeordnet. Den Weg, welcher durch die Züge der beiden Spieler beschrieben wird, nennt man eine Partie. Eine endliche Partie verliert der Spieler, der am Zug ist, wenn keine Züge mehr möglich sind. Bei einer unendlichen Partie bestimmt die Parität der höchsten Priorität der Partie, welcher der beiden Spieler gewinnt.
rdf:langString
En informatique théorique, un jeu de parité est un jeu à deux joueurs sur un graphe orienté où chaque sommet est étiqueté par un entier, appelé couleur ou priorité. Chaque joueur possède son propre sous-ensemble de sommets. Une partie est un chemin infini dans le graphe. Le premier joueur gagne lorsque la plus grande couleur visitée une infinité de fois est paire (chez certains auteurs, c'est lorsque la plus petite couleur visitée une infinité de fois est paire/impaire ; ces variantes sont fondamentalement équivalentes). Les jeux de parité sont importants en vérification de modèles, en particulier lorsque la propriété temporelle est exprimée en mu-calcul.
rdf:langString
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owner of the node that the token falls on selects the successor node, resulting in a (possibly infinite) path, called the play. The winner of a finite play is the player whose opponent is unable to move. The winner of an infinite play is determined by the priorities appearing in the play. Typically, player 0 wins an infinite play if the largest priority that occurs infinitely often in the play is even. Player 1 wins otherwise. This explains the word "parity" in the title. Parity games lie in the third level of the Borel hierarchy, and are consequently determined. Games related to parity games were implicitly used in Rabin'sproof of decidability of the monadic second-order theory of n successors (S2S for n = 2), where determinacy of such games wasproven. The Knaster–Tarski theorem leads to a relatively simple proof of determinacy of parity games. Moreover, parity games are history-free determined. This means that if a player has a winning strategy then that player has a winning strategy that depends only on the current board position, and not on the history of the play.
rdf:langString
パリティゲーム (parity games) は彩色された有向グラフ上でプレイされる理論上のゲームである。各ノードは優先度と呼ばれる(通常は有限種類の)自然数で彩色されている。このゲームはプレイヤー0とプレイヤー1の二名によってプレイされる。各プレイヤーは、ゲーム上に一個だけある駒をグラフの辺にそって動かす。手番は、その駒の現在地によって決められている。この操作を繰り返し(場合によっては無限回)行うことにより、プレイと呼ばれるパスが定まる。 有限長のプレイの場合、駒を動かせなくなったプレイヤーが敗者で、敗者でない側が勝者となる。無限長のプレイの勝者は、プレイ中に現れる優先度の値によって決定される。プレイ中に無限回現れた優先度のうち、最大の値が偶数ならばプレイヤー0の勝利、奇数ならばプレイヤー1の勝利となる。(偶奇が逆だったり、最大値のかわりに最小値を使う場合もある。) この偶奇性が「パリティ」の由来であろう。 パリティゲームはの3層目に属する。したがってパリティゲームは決定的である。 n後者演算に関する二階の理論の決定可能性に関するラビンの証明では、パリティゲームに類似のゲームが暗黙的に使われ、該当ゲームの決定性も証明されている。 を使えば、パリティゲームの決定性に対するより単純な証明を与えることもできる。 さらに、パリティゲームは履歴なしの決定性 (history-free determinacy, memoryless determinacy) をもつ。 これは、あるパリティーゲームの初期位置で、どちらかのプレイヤーが必勝戦略を持つとき、履歴なしの必勝戦略、すなわち今までの駒の動きに関係なく、現在位置だけで次の行き先を決めるような戦略、が存在するというものである。
rdf:langString
Gry parzystości – gry pomiędzy dwoma graczami, toczone na skierowanym grafie etykietowanym gdzie to zbiór wierzchołków grafu, a to zbiór jego krawędzi. Potencjalnie zbiór może być nieskończony. Gracze są z angielskiego nazywani Odd i Even. Każdy wierzchołek jest wierzchołkiem jednego z graczy, to znaczy to ten gracz wykonuje z niego ruch. Dana jest funkcja która każdemu wierzchołkowi przypisuje nieujemną liczbę całkowitą zwaną rankiem. Zakłada się, że obraz funkcji jest skończony. Gra polega na tym, że gracze wykonują ruchy (zgodne z krawędziami ze zbioru ) na grafie gry, w danym momencie rusza się ten, który jest właścicielem danego wierzchołka. Jeśli w pewnym momencie któryś z graczy nie może wykonać ruchu, to przegrywa, natomiast jeśli gra toczy się w nieskończoność, to przyglądamy się liczbie czyli największemu rankowi, który pojawia się na wybranej ścieżce nieskończenie wiele razy. Jeśli liczba ta jest parzysta, to wygrywa gracz Even, a jeśli nieparzysta, to gracz Odd.
xsd:nonNegativeInteger
10715
