Title: Theory / Unimportant / CS / Fundamental / Automata / Infinite / Perrin Pin+10 / 04 Games
Tags: fromMath mathToDef fromImplication automaticImplies hasSeenConjDef

Name: A game on \(A\)
Definition: A set \(X\subseteq A^\omega\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet

Name: A play in \(G(X)\)
Definition: An element of \(A^\omega\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet.

Question: A position in \(G(X)\) is
Answer: an element of \(A^*\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet
\(G(X)\) a game on \(A\)

Definition: The game starting at \(x\), \(G(u^{-1}X)\)
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet and \(G(X)\) a game on \(A\) and \(u\) a position
Notation: \(G_u(X)\)

Name: A strategy for player I
Definition: A function from \((A^2)^*\) to \(A\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet and \(G(X)\) a game on \(A\).

Name: A play of I, following the strategy
Definition: A play such that \(a_{2n}=f(a_0\dots a_{2n-1})\) for all \(n\in \mathbb N\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet,
\(G(X)\) a game on \(A\), and
\(f\) a strategy for player I.

Name: A winning strategy
Definition: A strategy for a player which wins all plays in which this payer follows \(f\).
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet, \(G(X)\) a game on \(A\), \(a_0a_1\dots\) a play.

Question: A player who
Answer: has a winning strategy.
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet, \(G(X)\) a game on \(A\)
Name: A player who wins the game

Name: A winning position for player \(p\)
Definition: A position \(u\) such that \(p\) wins the game \(G_u(X)\).
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet,
\(G(X)\) a game on \(A\),
\(p\) a player

Name: A determined game
Definition: One of the player has a winning strategy.
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet,
\(G(X)\) a game on \(A\).

Name: The restriction of \(G(X)\) to \(P\)
Definition: The game \(G(Y)\) where \(Y\) contains the word of \(X\) whose prefix of odd length belong to \(P\), and the word whose smallest prefix not belonging to \(P\) have even length.
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet, \(P\subseteq A^*\), \(G(X)\) a game on \(A\).

Smaller0: Player I wins \(G(X)\)
Greater0: player II
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet
\(G(X)\) a game on \(A\).
Smaller to greater: iff
Greater1: \(G(AX)\)
Connect Greater0: wins

Smaller0: Player II wins \(G(X)\)
Greater0: player I
Page: 189
Chapter: III
Section: 2
Variables: \(A\) an alphabet, \(G(X)\) a game on \(A\).
Smaller to greater: iff
Suffix Greater: wins \(G(a^{-1}X)\) for every \(a\in A\)

Name: A strategy for player II
Definition: A function from \((A^2)^*A\) to \(A\).
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet and \(G(X)\) a game on \(A\).

Smaller0: \(G\) is a borel game
Greater0: \(G\) is determined
Page: 190, 192
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(G\) a game on \(A\)
Index: 1, 2
Kind: Prop
Smaller1: \(G\) is closed
Name: Martin's theorem
Connect Smaller0: or
Name2: Wolfe's theorem (for \(\Pi_2\))

Definition: -\(U\) if \(i=0\)
otherwise:
--the set of elements of \(W_{i-1}\),
--\(w\in\left(A^2\right)^*\) if \(wa\in W_{i-1}\) for some \(a\in A\),
--\(w\in\left(A^2\right)^*A\) if \(wa\in W_{i-1}\) for every \(a\in A\).
Page: 190
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(U\) a game on \(A\),
\(i\in\mathbb N\)
Notation: \(W_i\)

Name: The rank function of \(U\)
Definition: [$]\defFun{A^*}{\mathbb N\cup\{\infty\}}{w}{\text{minimal $i$ such that $w\in W_i$}}[/$]
Page: 190
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(U\) a game on \(A\)
Denoted by: \(\rho\)

Smaller0: \(\rho(1)\) (the rank of the empty word) is finite
Greater0: player I has a finite strategy
Page: 191
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(U\) a game on \(A\)
Smaller to greater: iff

Question: \(W_0\)
Answer: Equals \(b^*a\)
Page: 191
Chapter: 3
Section: 1
Variables: \(U=b^*a\)

Question: The sequence of \(W_i\),s
Answer: \(b^*a\), \(b^*a\cup (bb)^*\), and infinitely often \(w^*a?\)
Page: 191
Chapter: 3
Section: 1
Variables: \(U=b^*a\)

Question: The winning strategy for I
Answer: Each turn, play such that the rank decrease
Page: 191
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,
\(U\) a game on \(A\)
\(w\in A^*\)
Assuming: \(\rho(w)\) is finite

Question: The winning stratety for II
Answer: Each turn, play such that the rank stay infinite
Page: 191
Chapter: 3
Section: 1
Variables: \(A\) an alphabet,Let \(U\) a game on \(A\)
\(w\in A^*\)
Assuming: \(\rho(w)=\infty\)

Name: The game of words on \(P\)
Definition: The game win by player 1 for play containing an element of \(P\).
\(G(A^*PA^\omega)\)
Page: 191
Chapter: 3
Section: 1
Variables: \(A\) an alphabet
\(P\subseteq A^*\)

Name: An I-imposed subgame on \(x\)
Definition: \(ua\in U\) for each \(a\in A\) and for each word \(u\in U\) of odd length.
Page: 192
Chapter: 3
Section: 2
Variables: \(A\) an alphabet,
\(x\in A^*\)
Definition2: \(\left(U^A(\left(A^2\right)^*\right)A\subseteq U\)
Conjdef: A set \(U\subseteq xA^*\) such that, equivalently

Name: Player II
Definition: plays the odd turns
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet and \(G(X)\) a game on \(A\).
Definition2: wins if the word does not belong to \(X\).
Conjdef: The player which
Name2: he

Name: Player I
Definition: play the even turns
Page: 188
Chapter: III
Section: 2
Variables: \(A\) an alphabet and \(G(X)\) a game on \(A\).
Definition2: wins if the word belongs to \(X\).
Conjdef: The player which
Name2: she