Title: Theory / Unimportant / CS / Fundamental / Complexity / Descriptive complexity+14 / Game
Tags: fromMath mathToDef mathToSee examplesSwitchExample1 automaticImplies closed equivalentHand toBinaryRelation typToBinary

Name: The game with \(k\) pebbles and \(m\) rounds on \(\mathcal A_0,\mathcal A_1\)
Definition: A game win by Duplicator if:
1)There is an isomorphism between the substructures of \(\mathcal A_0\) and \(\mathcal A_1\) induced by the constants and the function applied to them.
2) If \(m>0\), and for each assignment \(c_i\) of \(x_j\) for \(j<k\) in \(\mathcal A_i\), there is an assignment \(c_{i-1}\) of \(x_j\) in \(\mathcal A_{1-i}\) such that duplicator wins the game \(\mathcal G^k_{m-1}\) on \(\mathcal A_0[x_0/c_0]\) and \(\mathcal A_1[x_1/c_1]\).
Otherwise, it is win by Spoiler.
Page: 93
Chapter: 6
Section: 1
Variables: \(\tau\) a vocabulary
\(\mathcal A_0,\mathcal A_1\in STRUCT[\tau]\)
Notation: \(\mathcal G^k_m\)
Index: 6.2
Kind: Definition

Question: Immerman, page de 94 à 95
Answer: perdu
Page: 94

Name: The language of graph with a clique of size \(k\)
Page: 96
Chapter: 6
Section: 1
Variables: \(k\in\mathbb N\).
Notation: CLIQUE(\(k\))
Index: 13
Kind: Proposition
Extra: Example of \(\mathcal L^k(\tau_g) - \mathcal L^{k-1}(\tau_g)\)

Page: 93
Definition: Duplicator wins \(\mathcal G^k_m\) on \(\mathcal A_0,\mathcal A_1\).
Chapter: 6
Section: 1
Variables: \(\tau\) a vocabulary
\(\mathcal A_0,\mathcal A_1\in STRUCT[\tau]\).
Notation: \(\sim_m^k\)
Transitive: Equivalence relation

Question: ODD, on graphs with at least \(n\) vertices, require
Answer: at least \(n+1\) variables
Page: 97
Chapter: 6
Section: 1
Index: 14
Kind: Proposition

Name: \(\mathcal L^3_k(\tau_g) - \mathcal L_{k-1}(\tau_g,<)\)
Page: 97
Chapter: 6
Section: 1
Index: 15
Kind: Proposition
Example: The language of graph with a path of length at most \(2^k\) from \(x\) to \(y\)

Name: Language which can not be expressed with 2 variables, no matter the number of quantifications
Page: 98, 130
Chapter: 6
Section: 1
Index: 7
Kind: Theo
Example: The language of connected graph
Extra: -SO\(\exists\)(monadic)

Definition: \(S\) is not first-order describable on \(\mathcal C\)
Page: 99
Chapter: 6
Section: 2
Variables: \(\mathcal C\) be any class of finite or infinite structures of some finite, relation vocabulary.
\(S\subseteq\mathcal C\) be a boolean query on \(\mathcal C\).
Index: 19
Kind: Theorem
Definition2: For all \(r\in\mathbb N\), there exist structure \(\mathcal A_r,\mathcal B_r\in\mathcal C\) such that \(\mathcal A_r\in S,\mathcal B_r\not\in S\) and \(\mathcal A_r\sim_r\mathcal B_r\).

Name: The Gaifman graph of \(\mathcal A\)
Definition: The graph on \(|\mathcal A|\) with an edge between \(a\) and \(b\) if there exists \(i\in\mathbb N\), \(d_1,\dots,d_{a_i}\in R^{\mathcal A}_i\) such that \(a,b\in\{d_1,\dots,d_{a_i}\}\).
Page: 100
Chapter: 6
Section: 2
Variables: \(\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s\rangle\) a relational vocabulary
\(\mathcal A\) a \(\tau\)-structure
Context: Structure, logic
Notation: \(G_{\mathcal A}\)
Index: 20
Kind: Definition

Question: The Gaifman Graph of a graph \(G\) is
Answer: \(G\) itself.
Page: 100
Chapter: 6
Section: 2
Variables: \(G\) a graph.
Index: 20
Kind: Definition

Name: The universe of the neighborhood of element \(a\) at distance \(d\)
Definition: The set of \(b\in|\mathcal A|\) whose distance in the Gaifman graph is at most \(d\).
Page: 100
Chapter: 6
Section: 2
Variables: \(\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s\rangle\) a relational vocabulary
\(\mathcal A\) a \(\tau\)-structure
\(a\in\mathcal |A|\)
\(d\in\mathbb N\)
Notation: \(|N(a,d)|\)
Index: 20
Kind: Definition

Smaller0: for each possible \(2^r\)-type, \(t\), \(\mathcal A\) and \(\mathcal B\) have exactly the same number of elements of type \(t\)
Greater0: \(\mathcal A\equiv_r\mathcal B\)
Page: 100
Chapter: 6
Section: 2
Variables: \(\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s\rangle\) a relational vocabulary,
\(\mathcal A,\mathcal B\in\text{STRUC}[\tau]\) and
\(r\in\mathbb N\).
Index: 21
Kind: Theorem
Hide middle: yes
Name: Hanf's Theorem
Suffix Smaller: ,

Page: 101
Chapter: 6
Section: 2
Index: 24
Kind: Proposition
Name: Language which is not first-order expressible
-Acyclicity,
-2-colored,
-Connected,
-Reach.
Extra: Ex 26

Q: [...] is [...].
A: The degree of \(\mathcal A\); the degree of its Gaifman graph
Page: 102
Chapter: 6
Section: 3
Variables: \(\mathcal A\) a structure.

Name: \((n,s)\)-equivalent structures
Definition: Two structures \(\mathcal A\) and \(\mathcal B\) where, for each \(n\)-type \(\sigma\), \(\mathcal A\) and \(\mathcal B\) have the same number of neighborhoods of type \(\sigma\) or they both have more than \(s\) neighborhoods of type \(\sigma\).
Page: 102
Chapter: 6
Section: 3
Variables: \(\mathcal A,\mathcal B\) be structures and \(n,s\in\mathbb N\)

Smaller0: \(\mathcal A\) and \(\mathcal B\) are \((2^r,rd^{2^r}+1)\)-equivalent
Greater0: \(\mathcal A\equiv_r\mathcal B\)
Page: 102
Chapter: 6
Section: 3
Variables: \(r,d\in\mathbb N\)
\(\mathcal {A,B}\in\text{Struct}\) of degree at most \(d\)
Index: 27
Kind: Theorem
Hide middle: yes

Q: Over [...], \(\phi\) is recognisable in [...] time.
A: structures of bounded degrees; linear
Page: 103
Chapter: 6
Section: 3
Variables: \(\phi\in FO[<,bit]\)
Index: 29
Kind: Theorem

Name: A theory which have the \(k\)-variable property
Definition: A theory whose every formula is equivalent to a formula with \(k\) variables, up to \(\Sigma\).
Page: 104
Chapter: 6
Section: 4
Variables: \(\Sigma\) a theory
\(k\in\mathbb N\).
Index: 29
Kind: Theorem

Smaller0: for all models \(\mathcal A\) and \(\mathcal B\) of \(\mathcal S\) and all \(k\)-configuration \(\alpha,\beta\) of \(\mathcal A,\mathcal B\), \((\mathcal A,\alpha)\equiv_{\mathcal L'}(\mathcal B,\beta)\) implies that \((\mathcal A,\alpha)\equiv_{\mathcal L''}(\mathcal B,\beta) \)
Greater0: for all \(\phi\in \mathcal L''\) with free variables among \(x_1,\dots,x_k\) there exists \(\psi\in\mathcal L'\) such that \(\Sigma\models\phi\iff\psi\)
Page: 104
Chapter: 6
Section: 4
Variables: \(\Sigma\subseteq\mathcal L\) a first-order theory
\(k\in\mathbb N\)
\(\mathcal L',\mathcal L''\subseteq \mathcal L\) such that \(\mathcal L'\) is closed under the boolean connectives.
Index: 30
Kind: Lemma
Smaller to greater: iff
Hide middle: yes

Question: \(FO[<,R_1,\dots,R_n]\) with the \(R_i\)'s monadic
Answer: has the 3-variable property.
Page: 106
Chapter: 6
Section: 4
Index: 32
Kind: Theorem

Definition: The first-order formula stating that each \(k-1\) tuple can be extended to a \(k\)-tuple in any conceivable way.
Page: 108
Chapter: 6
Section: 5
Variables: M\(k\in\mathbb N\),
\(\tau=\{R_1^{a_1},\dots,R_n^{a_n}\}\) a vocabulary with only relation symbols.
\(A\) be the set of all atomic formulas of the form \(R_i(y_1,\dots,y_{a_i})\) such that \(x_k\in\{y_1,\dots,y_{a_i} \}\subseteq\{x_1,\dots,x_k\}\).
Notation: \(\gamma_k\)

Name: Zero-one law for \(\mathcal L^\omega_{\infty\omega}\)
Definition: Given a structure of cardinality \(n\), the probability that it satisfies \(S\) has limit either 0 or 1
Page: 108
Chapter: 6
Section: 5
Variables: \(k\in\mathbb N\)
\(\tau=\{R_1^{a_1},\dots,R_n^{a_n}\}\) a vocabulary with only relation symbols
\(S\subseteq\mathcal L^k\) any set of \(k\)-variables sentences over \(\tau\).

Smaller0: \(G\sim^3_{\lceil \log(n-1)\rceil +1} H \)
Greater0: \(G=H\)
Page: 109
Chapter: 6
Variables: \(G,H\) ordered graph and \(n=\text{max}(\parallel G\parallel,\parallel H\parallel)\).
Index: 43
Kind: Prop

Definition: The set of structures of even cardinal
Page: 110
Chapter: 6
Notation: EVEN
Index: 46
Kind: Cor

Q: To answer correctly over structures of cardinality at least \(n\), using only the < predicate, [...] needs quantifier rank at least [...]
A: EVEN and REACH; \(\lceil \log (n-1)\rceil \)
Page: 110
Chapter: 6
Index: 45
Kind: Prop
Extra: Note that there is no O(.) Cor46

Name: The \(d\)-type of \(a\)
Definition: the isomorphism type of \(N(a,d)\)
Page: 100
Chapter: 6
Section: 2
Variables: \(\tau=\langle R_1^{a_1},\dots,R_r^{a_r},c_1,\dots,c_s\rangle\) a relational vocabulary
\(\mathcal A\) a \(\tau\)-structure
\(a\in\mathcal |A|\) and
\(d\in\mathbb N\).
Index: 20
Kind: Definition