Title: Theory / Unimportant / CS / Fundamental / Automata / Number / rational base/ / Logic characterisation of p over q recognisable sets
Tags: closed fromMath mathToSee récupéré

Name: The canonical alphabet associated with base \(\frac pq\)
Definition: \(\{0,\dots, p-1\}\)
Page: 2
Section: 2.3
Variables: \(p/q\in\mathbb Q\)
Notation: \(A_p\)

Definition: The set of finite words over \(A_p\) whose interpretation is a natural.
Page: 1
Variables: \(p/q\in\mathbb Q\)
Notation: \(L_{\frac pq}\)

Definition: The set of interpretation of words of \((A_p)^*\)
Page: 1
Variables: \(p/q\in\mathbb Q\)
Notation: \(N_{\frac pq}\)
Definition2: \(\text{Val}((A_p)^*)\)

Name: A \(\frac{p}q\) recognisable set
Definition: a set realized by some automaton
Page: 1, 4
Section: 1
Variables: \(p/q\in\mathbb Q\)
Index: 2, b
Kind: , Theo

Definition: [$]\defFun{N_{\frac{p}q}}{N_{\frac{p}q}}{x}{\text{Greatest power of ${\frac{p}q}$ that one may divide $x$ by and obtain a quotient in $N_{\frac{p}q}$}}[/$]
Page: 1
Variables: \(p/q\in\mathbb Q\)
Notation: \(P_{\frac{p}q}\)

Definition: the representation of \(x\) is shorter than the representation of \(y\)
Page: 1
Variables: \(p/q\in\mathbb Q\)
\(x,y\in N_{\frac{p}q}\)
Notation: \(x\preceq y\)

Name: A padded automaton
Definition: An automaton which accepts a word \(\mathbf u\) iff it accepts \(\mathbf{0\cdot u}\).
Page: 2
Section: 2.1
Variables: \(p/q\in\mathbb Q\)

Definition: \(\sum_{i=0}^k \frac{a_i}q\left({\frac{p}{q}}\right)^l\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(a_k\dots a_0\in A_p^*\)
Notation: \(\text{Val}(a_k\dots a_0)\)
Index: 1

Smaller0: \(\text{Val}(a_k\dots a_0)\)
Greater0: \((a_k\dots a_{k'})\left({\frac{p}{q}}\right)^{k'}\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(a_k\dots a_0\in A_p^*\)
Index: 1
Smaller to greater: equals
Greater1: \(\text{Val}(a_{k'-1}\dots a_0)\)
Connect Greater0: +

Name: An expansion of \(x\)
Definition: A word whose valuation is \(x\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(x\in N_{\frac pq}\)
Index: 1

Name: The representation of \(x\)
Definition: The expansion of \(x\) not starting with 0
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(x\in N_{\frac pq}\)
Kind: theo
Abbreviation: \(\text{Rep}(x)\)
Cardinal: unique

Question: The representation of \(n\) in base p/q is
Answer: \(\text{Rep}(m)\cdot a\) with \(qn=pm+a\), or \(\epsilon\) if \(n=0\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(n\in\mathbb N\)
Index: 3b

Name: \(N_{\frac pq}\)
Page: 4
Section: 2.3
Index: 6
Variables: \(p/q\in\mathbb Q\),
Kind: prop
Under: addition
Condition: stable

Name: \(L_{\frac pq}\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
Extra: suffix
Under: prefix
Not2: not
Under2: rational

Name: A \(d\)-tape automaton realizing \(S\)
Definition: A \(d\)-tape automaton such that \(L(\mathcal A)=\mathbf 0^*\text{Rep}(S)\)
Page: 3
Section: 2.3
Variables: \(p/q\in\mathbb Q\),
\(d\in\mathbb N\)
\(S\subseteq\mathbb N^d\)
Index: 4
Kind: Def

Definition: The largest power \(y\) of \({\frac pq}\) such that \(xy^{-1}\in N_{\frac pq}\)
Page: 4
Section: 3
Variables: \(p/q\in\mathbb Q\),
\(x\in N_{\frac pq}\) not 0
Notation: \(V_{\frac pq}(x)\)
Index: 7
Kind: Def

Name: A \({\frac pq}\)-definable set
Definition: A \(FO\left[N_{\frac pq},+,V_{\frac pq},\preceq\right]\)-definable set
Page: 4
Section: 3
Variables: \(p/q\in\mathbb Q\),
Index: 7c
Kind: Def

Smaller0: \(X\) is \({\frac pq}\)-recognisable
Greater0: \(X\) is \({\frac pq}\)-definable
Page: 4
Section: 3
Variables: \(p/q\in\mathbb Q\),
\(X\subseteq N_{\frac pq}\)
Index: 2
Kind: Theo
Smaller to greater: iff