Title: Theory / Unimportant / CS / Fundamental / Automata / Infinite / Perrin Pin+10 / 10 Trees
Tags: fromMath mathToDef hasSeenConjDef closed mathToSee questionExample representation

Name: A problem
Definition: the initial state.
Page: 066
Chapter: 3
Section: 1.1
Definition2: description of the possible actions
Conjdef: A tuple containing
Definition3: the transition model
Definition4: the goal test
Definition5: the path cost

Name: A maximal filter
Definition: it is a maximal filter which is a strict subset of \(B\)
Page: 35
Chapter: 2
Section: 3
Variables: \((B,\land,\lor,\neg,0,1)\) a Boolean algebra
Definition2: for each \(x\in B\), it contains \(x\) xor \(\neg x\)
Conjdef: A filter \(F\) such that, equivalently
Name2: An ultrafilter

Name: A \(D\)-tree
Definition: A map \(t:P\to A\) with \(P\) a non-empty prefix-closed subset of \(D^*\).
Page: 414
Chapter: X
Section: 2
Variables: \(D,A\) two nonempty alphabets

Name: A node of \(t\)
Definition: An element of the domain of definition of \(t\).
Page: 414
Chapter: X
Section: 2
Variables: \(D,A\) two nonempty alphabets
\(t\) a \(D\)-tree

Name: A child of \(x\)
Definition: \(xi\) for some \(i\in D\).
Page: 414
Chapter: X
Section: 2
Variables: \(D,A\) two nonempty alphabets
\(t\) a \(D\)-tree
\(x\in \text{Dom}(t)\)

Name: Finite \(D\)-tree
Definition: A \(D\)-tree with finite model.
Page: 414
Chapter: X
Section: 2
Variables: \(D,A\) two nonempty alphabets.

Name: The height of \(t\)
Definition: The maximal length of \(\text{Dom}(t)\).
Page: 414
Chapter: X
Section: 2
Variables: \(D,A\) two nonempty alphabets
\(t\) a \(D\)-tree

Definition: \(\phi\circ t\)
Page: 414
Chapter: X
Section: 2
Variables: \(D,A,B\) nonempty alphabets,
\(t\) a \(D\)-tree
\(\phi:A\to B\)
Notation: \(\phi(t)\)

Name: A projection
Definition: A function from alphabet to alphabet.
Page: 414
Chapter: X
Section: 2
Variables: \(A,B\) nonempty alphabets.

Name: The frontier of \(t\)
Definition: \(\{x\in\text{Dom}(t)\mid xD\cap \text{Dom}(t)=\emptyset\}\).
Page: 415
Chapter: X
Section: 2
Variables: \(D,A,B\) nonempty alphabets
\(t\) a \(D\)-tree.
Notation: \(\text{Fr}(t)\)

Name: A leaf of \(P\)
Definition: An element of the frontier of \(P\)
Page: 415
Chapter: X
Section: 2
Variables: \((P,t)\) a tree
\(x\in P\).

Name: The outer frontier of \(t\)
Definition: \(PD-P\)
Page: 415
Chapter: X
Section: 2
Variables: \((P,t)\) a tree on domain \(D\).
Notation: \(Fr^+(t)\)

Definition: \(Dom(t)\cup Fr^+(t)\).
Page: 415
Chapter: X
Section: 2
Variables: \((P,t)\) a tree with directions \(D\).
Notation: \(Dom^+(t)\)

Name: A path through \(t\)
Definition: A maximal chain for the prefix order in \(Dom(t)\).
Page: 415
Chapter: X
Section: 2
Variables: \((P,t)\) a tree.

Definition: The restriction of \(t\) to \(\pi\).
Page: 416
Chapter: X
Section: 2
Variables: \((P,t)\) a tree and \(\pi\) a path
Notation: \(t\mid \pi\)

Name: An infinite tree
Definition: A tree whose domain is \(D^*\).
Page: 416
Chapter: X
Section: 2
Variables: \(D\) a set of directions

Definition: The set of finite binary trees on \(A\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
Notation: \(T_A\)

Definition: The set of infinite binary trees on \(A\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
Notation: \(T_A^\omega\)

Definition: \(T_A^*\cup T_A^\omega\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
Notation: \(T_A^\infty\)

Definition: The set of all trees obtained by replacing in a tree \(s\in S\) each occurrence of \(c\) on \(Fr(s)\) by a tree from \(T\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
\(S\subseteq T_A\),
\(T\subseteq T_A^\infty\)
\(c\in A\)
Notation: \(S\cdot _c T\)

Definition: \(\{c\}\) if \(n=0\), \(T\cdot _c T^{n-1,c}\cup T^{n-1,c}\) otherwise.
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
\(T\subseteq T_A\)
\(c\in A\)
\(n\in \mathbb N\).
Notation: \(T^{n,c}\)

Definition: \(\bigcup_{n\ge 0} T^{n,c}\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet, \(T\subseteq T_A\), \(c\in A\).
Notation: \(T^{*,c}\)

Name: Rational tree language
Definition: A language \(T\) of tree such that there is a finite set \(C\) containing \(A\) such that \(T\) can be obtained from finite subsets of \(T_C\) by finite number of unions, concatenations, \(\cdot _c\) and \(^{*,c}\) for \(c\in C\).
Page: 416
Chapter: X
Section: 2
Variables: \(A\) an alphabet
Example: \(T_A\)
Example2: Trees with \(a\) on the entier frontier

Question: Example of representation of \(S_n\) over \(F\)
Answer: Let \(V\) an \(n\)-dimensional \(F\)-vector space with basis \(e_1,\dots,e_{n}\).
The representation acts by permuting the subscripts of the basis elements: \(\sigma\mapsto (e_i\mapsto e_{\sigma i})\).
Page: 844
Chapter: 18
Section: 1
Variables: \(n\in\mathbb Z^+\),
\(F\) a field
Index: (3)
Kind: Ex

Name: A tree automaton
Definition: A finite set \(Q\) of states,
Page: 417
Chapter: X
Section: 3.1
Variables: \(A\) an alphabet
Definition2: A set \(E\subseteq Q\times A\times Q\times Q\) of edges
Conjdef: The tuple
Definition3: A set \(I\subseteq Q\) of initial state
Definition4: \(F\subseteq Q\) of final states

Name: A run of \(\mathcal A\)
Definition: \(r(\epsilon)\in I\)
Page: 417
Chapter: X
Section: 3.1
Variables: \(A\) an alphabet,
Let \(\mathcal A=(A,Q,E,I,F)\) a tree-automaton,
\(t\) a tree
Definition2: \((r(x),t(x),r(x0),r(x1))\in E\) for each \(x\in Dom(t)\)
Conjdef: A map \(Dom^+(t)\to Q\), with:
Denoted by: \(r\)

Name: A top-down deterministic tree automaton
Definition: \(|I|\le 1\),
Page: 418
Chapter: X
Section: 3.1
Definition2: for each \(p,a\in Q\times A\), there is at most one \((q,r)\in Q\times Q\) such that \((p,a,q,r)\in E\)
Conjdef: A tree automaton \(\mathcal A=(A,Q,E,I,F)\) such that

Name: A bottom-up deterministic tree automaton
Definition: \(|F|= 1\),
Page: 418
Chapter: X
Section: 3.1
Definition2: for each \((a,q,r)\in A\times Q\times Q\), there is at most one \((p)\in Q\) such that \((p,a,q,r)\in E\)
Conjdef: A tree automaton \(\mathcal A=(A,Q,E,I,F)\) such that

Name: A complete bottom-up deterministic tree automaton
Definition: A bottom-up deterministic tree automaton \(\mathcal A=(A,Q,E,I,F)\) such that:
-for each \((a,q,r)\in A\times Q\times Q\), there is exactly one \((p)\in Q\) such that \((p,a,q,r)\in E\)
Page: 419
Chapter: X
Section: 3.1

Name: The family of recognisable sets of trees
Page: 419
Section: 3.1
Chapter: X
Index: 1
Kind: Prop
Under: complement

Smaller0: \(T\) is recognisable
Greater0: \(T\) is rational
Page: 419
Chapter: X
Section: 3.1
Variables: \(A\) a variable
\(T\subseteq T_A\)
Index: 1
Kind: Prop
Smaller to greater: iff

Name: A recognisable set of finite trees
Definition: A set of trees accepted by a tree automaton
Page: 418
Chapter: X
Section: 3.1
Variables: \(A\) a variable
Kind: Prop