Title: Theory / Unimportant / CS / Fundamental / Automata / Number / Integral / any-dimensional / Logic and p-recognizable sets of integers
Tags: CorrectType EquivalentButNoIntermediate addIntermediateCard hasSeenConjDef toBinaryRelation

Name: Automata over \(A\) with output in \(B\)
Definition: A tuple \((Q,I,R,T)\) with \(Q\) a set of states, \(I\subseteq Q\) the set of initial state, \(R:Q\to B\) a labelling function and \(T\subseteq Q\times B\times Q\) the transition relation
Page: 3
Section: 2
Variables: \(A,B\) alphabets

Name: The function computed by \(\mathcal A\)
Definition: The set of \((w,b)\) with \(w\in A^*\), and \(b=R(q)\) with \((q_0,w,q)\in T^*\) , and \(q_0\in I\)
Page: 3
Section: 2
Variables: \(A,B\) alphabets
\(\mathcal A=(Q,I,R,T)\) an automaton over \(A\) with output in \(B\)

Page: 3
Definition: the relation on words \(u,v\in A^*\) such that for each \(w\in A^*\), \(uw\in L\iff vw\in L\)
Section: 2
Variables: \(A\) an alphabet
\(L\subseteq A^*\)
Notation: \(\sim_L\)
Transitive: right congruence

Name: A \(p\) substitution
Definition: A function \(B\to B^p\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
\(s:\mathbb N\to A\)

Definition: the concatenation \(f(a_1)\dots f(a_n)\) for \(w=a_1\dots a_n\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
\(s:\mathbb N\to A\)
\(f:A\to A^p\) a \(p\) substitution
\(w\in A^*\)
Notation: \(f(w)\)

Definition: the limit of the sequence \((f^n(b))_{n\ge 0}\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
\(s:\mathbb N\to A\)
\(f:A\to A^p\) a \(p\) substitution
\(a\in A\)
Notation: \(f^\omega(a)\)
Assuming: the first letter of \(f(b)\) is \(b\), for each \(b\in A\)

Name: A sequence generated by \(p\)-substitution
Definition: \(f^\omega(a)\), for \(A\) a finite alphabet, \(f:A\to A^p\) a \(p\)-substitution
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite

Name: A \(p\)-automaton
Definition: Complete deterministic finite automaton with output, whose transitions are labelled by \(\{0,\dots, p-1\}\), whose state are labelled by elements of \(A\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite

Name: A \(p\)-recognisable sequence
Definition: A sequence computed by some \(p\)-automaton
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite

Name: The sequence computed by \(\mathcal A\)
Definition: the sequence whose \(n\)-th element is the output of \(\mathcal A\) on the \(p\)-ary expansion of \(n\).
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
\(\mathcal A\) a \(p\)-automaton
Notation: \((n)_p\)

Name: The representation of \(n\) in base \(p\)
Definition: A word \(a_m\dots a_0\in\{0,\dots,p-1\}^*\) such that \(n=\sum_{i=0}^ma_ip^i\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(n\in\mathbb N\)

Definition: 0 to 1
Page: 9
Section: 2
Variables: \(p\ge2\)
Notation: \(V_p\)
Definition2: \(x>0\) to the greatest power of \(p\) dividing \(x\)
Conjdef: The function \(\mathbb N\to\mathbb N\)

Name: A \(p\)-definable sequence
Definition: A sequence \(s:\mathbb N\to A\) such that, for each \(a\in A\), the set of \(n\in\mathbb N\) such that \(s_n=a\) is \(\langle \mathbb N,+,V_p\rangle\)-definable
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite

Name: The power series associated to \(s\)
Definition: \(\sum s_nx^n\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq \mathbb F_p\) finite
\(s:\mathbb N\to A\)
Notation: \(S(x)\)
Assuming: \(p\) prime
DefType: The element \(\mathbb F_p[[x]]\)

Name: A \(p\)-algebraic sequence
Definition: \(S\) such that there exists polynomials \(q_i(x)\in\mathbb F_p[x]\) such that \(S(x)\) is a root of \(\sum_{j=0}^nq_j(x)t^j\)
Page: 9
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
Name2: A sequence algebraic over \(\mathbb F_p[x]\)
Assuming: \(p\) prime
DefType: The element \(\mathbb F_p[x][t]\setminus\{0\}\)

Smaller0: \(\mathbf s\) is generated by \(p\)-substitution
Greater0: \(\mathbf s\) is \(p\)-recognisable
Page: 10
Section: 2
Variables: \(p\ge2\)
\(A\subseteq N\) finite
\(\mathbf s:\mathbb N\to A\)
Kind: 1
Smaller to greater: iff
Smallest: \(\mathbf s\) is \(p\)-algebraic (assuming \(p\) is prime)
Intermediate: \(\mathbf s\) is \(p\)-definable