Title: Theory / Unimportant / CS / Fundamental / Automata / Number / Integral / any-dimensional / Leroux
Tags: récupéré fromMath mathToDef closed mathToSee list fromAlgorithm MissingMedia equivalentHand hasNotNewEffectReturnsMeaning oldAlgoNewName oldTypToDelete

Name: A boolean valuation
Definition: A function \(V\to\mathcal P(\mathbb Z^n)\)
Page: 004
Section: 2.1
Variables: \(V\) a set of variables,
Denoted by: \(\rho\)

Name: A boolean combination of sets in a class \(\mathcal C\) of sets
Definition: \(E\subseteq\mathbb Z^n\) such that there exists a boolean formula \(\phi(v_1,\dots,v_n)\) and some sets \(E_1,\dots,E_n\in\mathcal C\) such that \(E=\phi(E_1,\dots,E_n)\).
Page: 004
Section: 2.1

Name: The \(j\)th unit vector
Definition: [$](\underbrace{0,\dots,0}_{\texttt{$j$ times}},1,\underbrace{0,\dots,0}_{\texttt{$m-j-1$ times}})[/$]
Page: 004
Section: 2.2
Variables: \(1\le j\le m\) integers
Context: \(Q^m\)
Notation: \(e_{j,m}\in\mathbb Q^m\)

Name: The zero vector
Definition: The vector \(v\) such that \(v[i]\) equals 0 for all \(i\).
Page: 004
Section: 2.2
Variables: \(m\in\mathbb N\)
Notation: \(e_{0,m}\in\mathbb Q^m\)

Name: Infinite norm
Definition: \(\max_i |x[i]|\)
Page: 5
Section: 2.2
Notation: \(\parallel x\parallel_\infty\)

Definition: the least integer \(i\) such that \(n, d\le 2^{i}\).
Page: 005
Section: 2.2
Variables: \(\frac nd\in\mathbb Q\).
Notation: \(size(\frac nd)\)

Name: The set of \(r\)-digits
Definition: \(\{0,\dots,r-1\} \)
Page: 009
Section: 3.1
Variables: \(r\in\mathbb N\)
Notation: \(\Sigma_r\)

Name: The set of \(r\)-signs
Definition: \(\{0,r-1\}\)
Page: 009
Section: 3.1
Variables: \(r\in\mathbb N\)
Notation: \(S_r\)

Name: The set of \((r,m)\)-signs vectors
Definition: \(S_{r}^{m}\)
Page: 009
Section: 3.1
Variables: \(m,r\in\mathbb N\)
Notation: \(S_{r,m}\)

Name: The set of \((r,m)\)-digit vectors
Definition: \(\Sigma_{r}^{m}\)
Page: 009
Section: 3.1
Variables: \(m,r\in\mathbb N\)
Notation: \(\Sigma_{r,m}\)

Name: A \((r,m)\)-decomposition \((\sigma,s)\) of \(x\)
Definition: a couple \((\sigma,s)\in\Sigma_{r,m}^*\times S_{r,m}\) corresponding to a least significant digit first decomposition of \(x\) in basis \(r\).
Page: 009
Section: 3.1
Variables: \(m,r\in\mathbb N\) and \(x\in\mathbb Z^m\).

Definition: the restriction of \(\Gamma_{r,m,\sigma}\) to integers
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\)
\((\sigma,s)\in\Sigma_{r,m}^*\times S_{r,m}\)
Notation: \(\gamma_{r,m,\sigma}\)
Extra: 4.1
Typ: Unitary action of \(\Sigma_r^*\) to \(\mathbb Z^m\)

Definition: the restriction of \(\Gamma_{r,m,\sigma}\) to integers
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\)
\((\sigma,s)\in\Sigma_{r,m}^*\times S_{r,m}\)
Notation: \(\Gamma_{r,m,\sigma}\)
Index: 4.1

Name: \((r,m)\)-saturated language
Definition: A language \(\mathcal L\subseteq \Sigma_{r,m}^*\times S_{r,m}\), such that for any \((r,m)\)-decompositions \((\sigma_1,s_1)\) and \((\sigma_2,s_2)\) of the same vector, we have \((\sigma_1,s_1)\in\mathcal L\) iff \((\sigma_2,s_2)\in\mathcal L\).
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\).

Name: Saturated languages
Page: 010
Section: 3.1
Under: boolean combination.

Smaller0: \(S,T\) are saturated
Greater0: equals
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\).
Let \(S,T\subseteq\Sigma_{r,m}^*S_{r,m}\),
\(\#\)
Hide middle: yes
Prefix Greater: \(\rho_{r,m}(S\#T)\)
Suffix Greater: \(\rho_{r,m}(S)\#\rho_{r,m}(T)\)

Name: A (finite) digit vector graph
Definition: \(Q\) is the non-empty set of principale states
Page: 011
Section: 3.2
Index: 4
Kind: Def
Definition2: \(r\in\mathbb N\setminus\{0,1\}\) is the basis of decomposition
Definition3: \(m\in\mathbb N\setminus\{0\}\) is the dimension
Example2: A 5-tuple \(G=(Q,m,K,\Sigma_r,\delta)\) where
Abbreviation: ((F)DVG)
Definition4: \((K,\Sigma_r,\delta)\) (with \(K\) finite) is a graph such that \(Q\subseteq K\) and \(\delta(Q,\Sigma_{r,m})\subseteq Q.\)

Name: The size of \(G\)
Definition: \(r|K|\)
Page: 011
Section: 3.2
Variables: \(G=(Q,m,K,\Sigma_r,\delta)\) a FDVG
Index: 4
Kind: Def

Name: The parallelization of \(G\)
Definition: \((Q,\Sigma_{r,m},\delta)\).
Page: 011
Section: 3.2
Variables: \(G=(Q,m,K,\Sigma_r,\delta)\) a FDVG
Context: FDVG
Notation: \([G]\)
Index: 4
Kind: Def

Name: A (finite) final function
Definition: \(Q\) is the (finite) non empty set of principlal state
Page: 011
Section: 3.2
Index: 5
Kind: Def
Definition2: \(r\in\mathbb N\setminus\{0,1\}\) is the basis of decomposition
Definition3: \(m\in\mathbb N\setminus\{0\}\) is the dimension
Example2: A tuple \(F=(Q,f,m,K,S_r,\delta,K_F)\)
Definition4: \((K,S_r,\delta)\) is a finite graph
Definition5: \(f:Q\to K\) is a function mapping principal states to states in \(K\)
Definition6: \(K_F\subseteq K\) is the set of final states
Definition7: the language recognized by the automaton \((f(q),K,S_r,\delta,K_F)\) is a subset of \(S_{r,m}\) for any principal state \(q\in Q\)

Name: A final function compatible with \(G\)
Definition: A final function \(F\) which is defined over the same set of principal states with the same basis and the same dimension as \(G\)
Page: 011
Section: 3.2
Variables: \(G\) a DVG.

Definition: The language of \((r,m)\)-decompositions:
\[\{(w,s)\in\Sigma_{r,m}^*\times S_{r,m}; s\in[F](\delta(q,w))\}.\]
Page: 011
Section: 3.2
Variables: \(G\) a DVG
\(F\) a compatible final function.
Notation: \(\mathcal L((q,G,F))\)

Name: Saturated final function
Definition: is compatible with \(G\)
Page: 011
Section: 3.2
Variables: \(G\) a DVG
\(F\) a final function
Definition2: \(\mathcal L((q,G,F))\) is \((r,m)\)-saturated for any principal state \(q\in Q\).
Conjdef: A final function which

Definition: \[\sum_{n=1}^\infty \frac {1}{n^s} \]
Notation: \[\zeta(s)\]

Name: A (Finite) digit vector automaton
Definition: \(G\) a (F)DVG
Page: 012
Section: 3.2
Index: 7
Kind: Definition
Definition2: \(q_0\) a state
Definition3: \(F_0\) a (finite) final function saturated for \(G\).
Abbreviation: (F)DVA
DefType: A tuple

Definition: The DVA obtained from \(\mathcal A\) by replacing the initial state \(q_0\) by \(q\in Q\).
Page: 015
Section: 4.1
Variables: \(\mathcal A\) be an automaton
\(q\) be a principal state of \(\mathcal A\).
Notation: \(\mathcal A_q\)

Definition: The set represented by \(\mathcal A_q\).
Page: 015
Section: 4.1
Variables: \(\mathcal A\) a DVA
\(X\) a set represented by \(\mathcal A\)
Notation: \(X_q\)

Definition: [$]\defFun{\Sigma^+_{r,m} }{\mathbb Q^r}{\sigma}{\frac{\gamma_{r,m,\sigma}(e_{0,m})}{1-r^{|\sigma|_m} } }[/$].
Page: 017
Section: 4.1
Variables: \(r,m\in\mathbb N\).
Notation: \(\xi_{r,m}\)
Index: 4
Kind: Lemma
Applied to3: the unique fix-point of \(\Gamma_{r,m,\sigma}\).

Definition: the set represented by the DVA \(\mathcal A^F\) obtained from \(\mathcal A\) by replacing \(F_0\) by \(F\).
Page: 017
Section: 4.2
Variables: \(X\) a set implicitely represented by a DVA \(\mathcal A\), and \(F\) a final function saturated for \(G\).
Notation: \(X^F\)

Name: A set \((r,m)\)-detectable in \(X\)
Definition: for all \(\sigma_1,\sigma_2\in\Sigma_{r,m}^*\), having \(\gamma^{-1}_{r,m,\sigma_1} (X)=\gamma^{-1}_{r,m,\sigma_2} (X)\) implies
\(\gamma^{-1}_{r,m,\sigma_1} (X')=\gamma^{-1}_{r,m,\sigma_2} (X')\)
Page: 017
Section: 4.2.1
Variables: \(r,m\in\mathbb N\),
\(X\subseteq\mathbb Z^m\).
Definition2: for any DVA \(\mathcal A\) that represents \(X\), there exists a final function \(F\) saturated for \(G\) such that \(X'=X^F\).
Example2: A set \(X'\) such that

Page: 018
Implementation: Creates a heap of \(\sigma_{q,i}\) ordered by size
Add \(\sigma_{q_0,0}=\epsilon\),
For each \(\sigma_{q,i}\) in the heap:
-for each \(\sigma_{\delta(q,a),i+1}\):
--if it is already defined, continue
--Otherwise:
---set \(\sigma_{\delta(q,a),i+1}\) to \(\sigma_{q,i}a\)
---add \(\sigma_{\delta(q,a),i+1}\) to the heap
Section: 4.2.1
Variables: \(m,r\in\mathbb N\)
\(\mathcal A\) a FDVA with \(n\) states.
Name: \(U\)
Time complexity: P
Returns: The set of \(\sigma_{q,i}\) when they exists
Index: 6
Kind: Prop

Definition: \(\delta(q_0,w)=q\)
Page: 018
Section: 4.2.1
Variables: \(\mathcal A\) a FDVA with \(n\) states.
\(q\in K\),
\(i\in[m-1]\)
Notation: \(\sigma_{q,i}\)
Index: 6
Kind: Prop
Definition2: [$]\abs{w}\le n[/$]
Definition3: [$]\abs{w}\equiv  i\mod m[/$]
Example2: An arbitrary word \(w\) over \(\Sigma_{r}\)
Extra: Il n'est pas prouvé que <n est possible. Ça semble vrai uniquement si K est partitionné avec exactement \(Q=\delta(q_0,w)\) avec \(w\in\Sigma_{r,m}^*\), sinon il faut multiplier par m au moins la longueur

Question: The size of \(U\) is
Answer: at most \(rmn\)
Page: 018
Section: 4.2.1
Variables: \(\mathcal A\) a FDVA with \(n\) states.
\(X'\) be a set.
Index: 6
Kind: Prop

Definition: The set of vectors \(x\in\mathbb Z^m\) having a \((r,m)\)-decomposition of the form \((\sigma,s)\) where \(\sigma\in\Sigma^*_{r,m}\).
Page: 019
Section: 4.2.1
Variables: \(r>1, m>0,s\in S_r\).
Notation: \(Z_{r,m,s}\)
Definition2: \[\bigwedge_{i;s[i]=0}x[i]\ge 0\land \bigwedge_{i;s[i]=r-1}x[i]< 0\]

Name: An \(s\)-eye
Definition: An \(\sim_s\)-equivalence class \(Y\subseteq Q\).
Page: 020
Section: 4.2.2
Variables: FDVG \(G=(Q,m,K,\Sigma_r,\delta)\)
\(s\in S_{r,m}\).

Name: \(s\)-kernel
Definition: A non empty set of the form \(\{q_1,\dots,q_k\}\) such that \(\delta(q_{i},s)=q_{i+1\mod k}\).
Page: 020
Section: 4.2.2
Variables: FDVG \(G=(Q,m,K,\Sigma_r,\delta)\),
\(s\in S_{r,m}\)
\(Y\) an \(s\)-eye.
Abbreviation: \(ker_s(Y)\)

Name: A \(r\)-definable set
Definition: A \(FO(\mathbb Z,+,V_r)\)-definable set.
Page: 021
Section: 5.1
Variables: \(r>1\).

Definition: [$]\defFun{\mathbb Z^m}{\mathbb Z^m}{\vec x}{x[i]\text{ if $s[i]=0$, }-1-x[i]\text{ otherwise}}[/$]
Page: 021
Section: 5.1
Variables: \(r>1\),
\(m>0\)
\(s\in S_{r,m}\)
Notation: \(f_{r,m,s}\)

Name: A \((r,m,\sigma)\)-cyclic set
Definition: \(\gamma^{-1}_{r,m,\sigma}(X)=X\).
Page: 017, 027
Section: 4.1, 7.1
Variables: \(r>1, m>0\),
\(\sigma\in\Sigma_{r,m}^+\).
Index: ,2
Kind: ,Lemma
Definition2: (Assuming \(X\) is accepted by an automaton)\(X\) is accepted by a \((r,m,\sigma)\)-cyclic automaton.
Definition3: (assuming \(X\) Presburger-definable) \(X\) is defined by a boolean combination of formulas of the form \(\langle \alpha,x-\xi_{r,m}(\sigma)\rangle<0\) with \(\alpha\in\mathbb Z^m\), and \(x\in b+n\mathbb Z^m\) with \(b\in\mathbb Z^m\), \(n\) coprime to \(r\).
Example2: A set \(X\subseteq\mathbb Z ^m\) such that

Definition: \(\rho_{r,m}(\mathcal L_{k,q},\mathrm{e}_{0,m})\)
Page: 029
Section: 7.1
Variables: \(r>1, m>0\),
\(\mathcal A\) an FDVA
\(X\) the set it represents,
[$]0\le k<\abs{Q}[/$]
\(q\in Q\)
Notation: \(X_{k,q_c}\)
Index: 3
Kind: Prop

Name: A cyclic subset of \(\mathbb Z^m\)
Definition: A \((r,m,\sigma)\)-cyclic for some \(\sigma\in\Sigma^+_{r,m}\).
Page: 027
Section: 7.1
Variables: \(r>1, m>0\)
Definition2: \(\gamma^{-1}_{r,m,\sigma}(X)=X\)

Definition: The set of principal states of \(\mathcal A\)
Page: 027
Section: 7.1
Variables: \(r>1, m>0\),
\(\mathcal A\) an FDVA
Notation: \(Q_c\)
Definition2: \(\gamma^{-1}_{r,m,\sigma}(X)=X\)

Definition: The function sending \(x\in\mathbb Z^m\) to the sign digit \(s\in S_{r,m}\) such that \(x\in Z_{r,m,s}\)
Page: 029
Section: 7.1
Variables: \(r>1, m>0\),
Notation: \(\text{sign}\)
Index: 5
Kind: Prop

Definition: The set of \(\sigma\in\Sigma^k_{r,m}\) such that \(\delta(q_0,\sigma)=q\)
Page: 029
Section: 7.1
Variables: \(r>1, m>0\),
\(\mathcal A\) an FDVA
\(X\) the set it represents,
[$]0\le k<\abs{Q}[/$]
\(q\in Q\)
Notation: \(\mathcal L_{k,q}\)
Index: 3
Kind: Prop

Page: 28
Section: 7.1, 7.2
Notation: A Presburger formula defining the set accepted by \(\mathcal A\)
Variables: \(\mathcal A\) be a FDVA.
Name: P
Example: For each [$]0\le k<\abs{Q}[/$], \(q\in Q\) computes \(\mathcal L_{k,q}\)
Computes \(\phi_{k,q_c}(x)\) defining \(X_{k,q_c}\)
Returns [$]\bigvee_{q_c\in Q_c}\bigvee_{k=0}^{\abs{Q}-1}(\exists y,z((x=r^k\cdot y+z)\land\phi_{q_c}(y)\land\phi_{k_{q_c}}(z)))[/$]
Kind: Prop
Index: 4
Context: for each cyclic principal state \(q_c\), \(\mathcal A_q\) is defined by a Presburger formula \(\phi_{q_c}\)

Page: 028, 29
Section: 7.1, 7.2
Notation: a Presburger formula defining the set accepted by \(\mathcal A\)
Variables: \(\mathcal A\) be a FDVA.
Name: P
Kind: Prop
Index: 5
Context: for each principal state \(q\) accessible in a step, \(\mathcal A_q\) is defined by a Presburger formula
Extra: found nowhere

Page: 29
Section: 7.2
Notation: a Presburger formula defining the set accepted by \(\mathcal A\)
Variables: \(\mathcal A\) be a FDVA.
\(X\) the set defined by \(\mathcal A\)
\(S\subseteq S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Name: P
Example: Reduce to the case with a loop on initial state
Return\[\bigvee_{C\in\mathcal C}(\text{sign}(x)\in[F_0](C)\land\forall N\exists n\ge N\mathcal R_C(\theta_s(x,1+n)\land W_s(x,n))_{s\in S})\]
Kind: Prop
Index: 5
Context: for each \(q,q'\in Q\) such that \(F_0(q)\ne F_0(q')\),  \(F_0(q)\Delta F_0(q')\) intersects \(S\)

Page: 028
Section: 7.1
Notation: A Presburger formula defining the set accepted by \(\mathcal A\)
Variables: \(\mathcal A\) be a FDVA.
Name: P
Example: A formula stating that the \(i\)-th step reads \(b_{i}\in\Sigma_{r,m}\), for [$]0\le i\le \abs{Q}[/$], and that [$]x=\sum_{i=0}^{\abs{Q}}b_{i}+r^i[/$]
Kind: Lem
Index: 3
Context: \(\mathcal A\) accepts a finite language

Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Notation: \(\theta_{s}(x,k)\)
Index: 5
Kind: Lem, Prop
Applied to3: the set of \(x\) such that \(x+k\frac{s-\text{sign}(x)}{1-r}\) belongs to \(Z_{r,m,s}\cap X\)

Definition: The least integer \(m\) such that \(K_{s,x}\) is ultimately \(m\)-periodic
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(x\in\mathbb Z^m\)
Notation: \(n_{s,x}\)
Index: 5
Kind: Lem, Prop
Property: Relatively prime with \(r\)

Definition: The set of \(k\in\mathbb Z\) such that \(\theta_s(x,k)\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(x\in\mathbb Z^m\)
Notation: \(K_{s,x}\)
Index: 5
Kind: Lem, Prop

Definition: The threshould of \(n_{s,x}\)-periodicity
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(x\in\mathbb Z^m\)
Notation: \(k_{s,x}\)
Index: 5
Kind: Lem, Prop

Definition: The subset of \(\{0,n_{s,x}-1\}\) such that \(K_{s,x}\cap (k_{s,x}+\mathbb N)=k_{s,x}+B_{s,x}+n_{s,x}\mathbb N\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(x\in\mathbb Z^m\)
Notation: \(B_{s,x}\)
Index: 5
Kind: Lem, Prop

Definition: \(n\ge 1\land \exists k_0\forall x\ge k_0; \theta_s(x,k)\iff \theta_s(x,k+n)\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Notation: \(W_{s}(x,n)\)
Index: 5
Kind: Lem, Prop
Applied to3: a formula defining \(n_{s,x}(\mathbb N\setminus \{0\})\)

Definition: \(n\ge 1\land \exists k_0\forall x\ge k_0; \theta_s(x,k)\iff \theta_s(x,k+n)\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Notation: \(W_{s}(x,n)\)
Index: 5
Kind: Lem, Prop
Applied to3: A formula defining \(n_{s,x}(\mathbb N\setminus\{0\})\)

Definition: the equivalence relation on states \(q_1,q_2\) such that \(F_0[q_1]=F_0[q_2]\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Context: States
Notation: \(\sim\)
Index: 5
Kind: Lem, Prop

Name: The set of \(\sim\)-equivalence class
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
Context: States
Notation: \(\mathcal C\)
Index: 5
Kind: Lem, Prop

Definition: \(F_0[q]\) for an arbitrary \(q\in C\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(C\in\mathcal C\)
Context: States
Notation: \([F_0](C)\)
Index: 5
Kind: Lem, Prop

Definition: A boolean formula such that \(C\) is defined by \(\mathcal R_C([F_0](q)_{s\in S})\)
Page: 29
Section: 7.2
Variables: \(\mathcal A\) be a FDVA.
\(s\in S_{r,m}\)
\(\phi_s(x)\) a definition of \(\mathbb N^m\cap f_{r,m,s}(X)\)
\(C\in\mathcal C\)
Context: States
Notation: \(\mathcal R_C\)
Index: 5
Kind: Lem, Prop

Name: The vector hull of \(X\)
Definition: The smallest vector space containing \(X\).
Page: 035
Section: 8.1
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).
Definition2: the set of \(\sum a_ix_i\) with \(a_i\in\mathbb R\) and \(x_i\in X\)
Abbreviation: \(VEC(X)\)

Name: A full rank for a vector space \(V\)
Definition: A set \(I\subseteq \{1,\dots,m\}\) such that, for any \(x\in\mathbb Q^I\) there exists a unique \(v\in V\) such that \(v[i]=x[i]\) for any \(i\in I\).
Page: 036
Section: 8.1
Variables: \(m\in\mathbb N\),
\(I\subseteq \{1,\dots,m\}\), and
\(V\subseteq\mathbb Q^m\) a vector space.

Question: The number of full rank set of indices of \(V\) is
Answer: at least one
Page: 036
Section: 8.1
Variables: \(m\in\mathbb N\)
\(V\subseteq \mathbb Q^m\) a vector space.
Kind: Prop

Name: A vector \(I\)-representation of a vector space
Definition: A sequence \((v_i)_{i\in I}\) satisfying \(v_i[i]=1\) and \(v_i[j]=0\) for \(j\in I\setminus\{i\}\).
Page: 036
Section: 8.1
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\) a vector space, and
\(I\)  a full rank set of indices for \(V\).
Typ: exactly one such set
A base of \(V\)

Question: \(x-\sum_{i\in I}x[i]v_i\) is
Answer: not zero.
Page: 036
Section: 8.1
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\) a vector space
\(I\) a full rank set of indices for \(V\)
\(x\in\mathbb Q^m\setminus V\),
\(V'=V+\mathbb Q x\).
v?
Index: 8.2
Kind: Prop

Page: 036
Section: 8.1
Notation: a full rank set of indices \(I'\) for \(V'\)
the vector \(I\)-representation of \(V'\)
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\) a vector space
\(I\) a full rank set of indices for \(V\)
\(x\in\mathbb Q^m\setminus V\),
\(V'=V+\mathbb Q x\).
\(y=x-\sum_{i\in I}x[i]v_i\)
\(j\in[m]\)
Example: \(I\cup\{j\}\) \(\left(v_j-v_j[j_0]\frac{y}{y[j_0]}\right)\) and \(\frac{y}{y[j_0]}\)
Kind: Prop
Index: 8.2
Context: \(y[j]\ne0\).

Question: The size of \(V\) is
Answer: at most polynomially larger than the size of any finite subset \(V_0\subseteq \mathbb Q^m\) that generates \(V\)
Page: 037
Section: 8.1
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\) a vector space
Index: 3
Kind: Cor

Name: The direction of \(A\)
Definition: The only vector space \(V\) such that \(A=a+V\).
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\),
\(A\subseteq \mathbb Q^m\) an affine space.
Notation: \(\vec A\)

Name: The size of a vector space \(V\)
Definition: \(\max_{I}(\sim_{i\in I}\text{size}(v_i))\)
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\), \(V\subseteq \mathbb Q^m\) a vector space.

Name: The size of \(A\)
Definition: \(\max_{I}(\text{size}(a)+\sum_{i\in I}\text{size}(v_i))\) where \((a,(v_i)_{i\in I})\) is the unique \(I\)-affine representation of \(A\).
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\),
\(A\subseteq\mathbb Q^m\) an affine space.

Name: Its affine hull
Definition: The smallest affine set containing \(X\).
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).
Abbreviation: \(aff(X)\)

Name: The group generated by \(X\)
Definition: The smallest group set containing \(X\).
Page: 038
Section: 8.3
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).
Abbreviation: \(group(X)\)

Name: A vector lattice
Definition: finitely generated
Page: 039
Chapter: 8
Section: 8.3
Variables: \(m\in\mathbb N\) and \(X\subseteq \mathbb Q^m\).
Index: 5
Kind: Prop
Definition2: discrete
Conjdef: A group which is

Name: A discret subset of \(\mathbb Q^m\)
Definition: A set \(M\subseteq \mathbb Q^m\) such that, for all \(x\in M\) there exists a rational \(\epsilon>0\) such that \(\parallel x-y\parallel _\infty\ge\epsilon\) for any \(y\in M\setminus \{x\}\).
Page: 039
Section: 8.3
Variables: \(m\in\mathbb N\).

Name: An Hermite matrix \(B\) of order \(d\)
Definition: A lower triangular non-negative square matrix \(B\in\mathcal M_{d,d}(\mathbb Q_+)\) in which each row has a unique maximal entry which is located on the main diagonal of \(B\)
Page: 040
Section: 8.3.1
Variables: \(d\in\mathbb N\).

Page: 040
Section: 8.3.1
Notation: The unique Hermite \(I\)-representation of \(M\)
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space,
\(I\) a full rank set of indices of \(V\)
\(M\) a \(V\)-vector lattices.
Name: P
Example: Theo 4.1, 4.2, 5.3 from Sch87
Kind: Theorem
Index: 6

Page: 040
Section: 8.3.1
Notation: Hermite \(I\)-representation of the \(V\)-vector lattice \(\mathbb z^m\cap V\).
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space
\(I\) a full rank set of indices of \(V\).
Chapter: 8
Name: P
Example: Cor 5.3b,c of Sch87
Kind: Proposition
Index: 7

Name: The class of \(V\)-vector lattices
Page: 41
Section: 8.3.2
Index: 8
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
Kind: Lemma
Under: intersection
Condition: finite
Under2: product

Name: The class of \(V\)-vector lattices
Page: 041
Section: 8.3.2
Index: 9
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
Kind: Remark
Not: not
Under: infinite intersection.
Under2: Union
Condition2: (finite or infinite)?

Name: The quotient of \(M'\) by \(M\)
Definition: \(\{m'+M;m'\in M\}\).
Page: 041
Section: 8.3.3
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
\(M\subseteq M'\) \(V\)-vector lattices.
Notation: \(M'/M\)

Name: A characteristic sequence of \(M\) in \(M'\)
Definition: \(n_i|n_{i+1}\)
Page: 041
Section: 8.3.3
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
\(M\subseteq M'\) \(V\)-vector lattices.
Index: 10
Kind: Theo
Definition2: \(v_1,\dots,v_d\) is a \(\mathbb Z\)-basis of \(M'\)
Definition3: \((n_iv_i)_{1\le i\le d}\) is a \(\mathbb Z\)-basis of \(M\)
Example2: sequences \(n_1,\dots,n_d\in\mathbb N\setminus 0\)
\(v_1,\dots,v_d\in M'\)
Typ: exactly one

Page: 041
Section: 8.3.3
Notation: A characteristic sequence of \(M\) in \(M'\)
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
\(M\subseteq M'\) \(V\)-vector lattices.
Name: \(P\)
Example: Tau92
Kind: Theo
Index: 10

Definition: \(\frac{n}{\gcd(n,r)}\).
Page: 041
Section: 8.3.4
Variables: \(n,r\in\mathbb N^{>0}\).
Notation: \(h_r(n)\)

Definition: The predecessor of \(i\) modulo \(m\).
Page: 041
Section: 8.3.4
Variables: \(m\in\mathbb Z^+\),
\(0<i\le m\)
Notation: \(\theta_m(i)\)

Definition: \(\gamma^{-z}_{r,m,0}(M)\).
Page: 042
Section: 8.3.4
Variables: \(m,z\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
\(M\subseteq\mathbb Z^m\) be a \(V\)-lattice.
Notation: \(M_z\)
Index: 13
Kind: Prop
Typ: a \(\Gamma^{-z}_{r,m,0}(V)\)-lattice included in \(\mathbb Z^m\)

Page: 042
Section: 8.3.4
Notation: The \(\theta^z_m(I)\)-representation of \(M_z\).
Variables: \(m,z\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space
\(M\subseteq\mathbb Z^m\) be a \(V\)-lattice.
\(H\) an Hermite \(I\)-representation of \(M\)
Name: P
Kind: Prop
Index: 13
Extra: todo

Name: The affine hull over \(\mathbb D\) of \(S\)
Definition: \(\{\sum_{i=1}^k a_i x_i\mid a_i\in D, \sum_{i=1}^k a_i=1\} \).
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\),
\(S\subseteq\mathbb Q^m\) be a set
\(\mathbb D\in\{\mathbb Q,\mathbb Z\}\).
Definition2: the smallest set containing \(S\) of elements satysfying a conjunction of linear equations (assuming \(\mathbb D=\mathbb Q\))
Definition3: the smallest set containing \(S\) of elements satysfying a conjunction of linear equations and of congruence equation (assuming \(\mathbb D=\mathbb Z\))

Name: A \(V\)-vector lattice relatively prime with a basis of decomposition \(r\)
Definition: A \(V\)-vector lattice \(M\) such that the integer \(|\left(\mathbb Z^m\cap V\right)/M|\) is relatively prime with \(r\).
Page: 043
Section: 8.3.4
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space.

Name: The class of \(V\)-vector lattice \(M\subseteq\mathbb Z^m\) which are relatively prime with a basis of decomposition \(r\)
Page: 043
Section: 8.3.4
Variables: \(m,r\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space.
Under: intersection
Condition: Which ?
Under2: inverse image by \(\gamma_{r,m,\mathbf{e}_{0,m}}\)
Under3: union
Condition3: Finite ?

Name: \(h^\infty_r(n)\)
Definition: \(\lim_{k\to\infty} h^k_r(n)\)
Page: 043
Section: 8.3.4
Variables: \(n,r\in\mathbb N\)
Property: Relatively prime with \(r\)

Name: A \(V\)-affine lattice
Definition: A lattice of the form \(a+M\) where \(M\) is a \(V\)-lattice and \(a\in\mathbb Q^m\).
Page: 044
Section: 8.4
Variables: \(m\in\mathbb N\), \(V\subseteq\mathbb Q^m\) a vector space.

Question: \(\mathbb Z^m\cap A\) is
Answer: either empty or a \(V\)-affine lattice
Page: 044
Section: 8.4
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space
\(A\) a \(V\)-affine space.
Index: 15
Kind: Prop

Question: It is possible to
Answer: compute in P a vector in \((b_1+M_1)\cap (b_2+M_2)\) if one such exists.
Page: 044
Section: 8.4
Variables: \(m\in\mathbb N\), for \(i\in\{1,2\}\), \(M_i\) a vector lattice and \(b_i\in\mathbb Q^d\).
Index: 16
Kind: Cor

Name: A semi-affine (vector) space
Definition: A finite union of affine (vector) space.
Page: 045
Section: 9.1
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Q^m\)

Name: A semi-\(V\)-affine space
Definition: A finite union of \(V\)-affine space.
Page: 045
Section: 9.1
Variables: \(m\in\mathbb N\), \(V\subseteq\mathbb Q^m\) a vector space, \(X\subseteq\mathbb Q^m\)

Name: An affine component \(S\)
Definition: A \(\subseteq\)-maximal affine space included in \(S\).
Page: 046
Section: 9.1.1
Variables: \(m\in\mathbb N\), \(S\subseteq \mathbb Q^m\) a semi-affine space.
Index: 1
Kind: Definition

Name: The direction of \(S\)
Definition: \(\bigcup_{a\in\text{comp}(S)}\vec A\).
Page: 047
Section: 9.1.3
Variables: \(m\in\mathbb N\), \(S\subseteq \mathbb Q^m\) a semi-affine space.
Notation: \(\overrightarrow{S}\)
Index: 4
Kind: Def

Name: The semi-affine hull of \(X\)
Definition: The smallest semi-affine superset of \(X\).
Page: 47
Section: 9.1.4
Variables: \(m\in\mathbb N\), \(X\subseteq \mathbb Q^m\) a semi-affine space.
Abbreviation: \(\text{saff}(X)\)

Name: The semi-vector space of its semi-affine hull
Definition: \(\overrightarrow{\text{saff} (X)}\).
Page: 047
Section: 9.1.4
Variables: \(m\in\mathbb N\)
\(X\subseteq \mathbb Q^m\) a semi-affine space
Notation: \(\overrightarrow{\text{saff} }(X)\)

Question: The sequence \((\gamma^{-k}_{r,m,e_{0,m} }(M))_{k\in \mathbb N}\) is
Answer: ultimately stationary.
Page: 043
Section: 9.1.4
Variables: \(m,r\in\mathbb N\)
\(V\subseteq\mathbb Q^m\)
\(M\subseteq\mathbb N^m\) a \(V\)-vector lattice.

Question: The function saff is an automorphism of
Answer: \((\mathbb Q^m,+)\),
Page: 048
Section: 9.1.4
Answer2: \((\mathbb Q^m,\cup)\)
Index: 9
Kind: Lemma
Answer3: \((\mathbb Q^m,\times)\) (cartesian product)

Name: A semi-\(V\)-affine lattice
Definition: A finite union of \(V\)-affine lattices.
Page: 050
Chapter: 9.2
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space

Name: The class of semi-\(V\)-affine spaces
Page: 047
Section: 9.1.4
Index: 6
Variables: \(m\in\mathbb N\), \(V\subseteq\mathbb Q^m\) a vector space.
Kind: Proposition
Under: union
Condition: finite
Under2: intersection
Condition2: arbitrary
Under3: \(\gamma^{-1}_{r,m,w}\)?

Question: \(P\) is of the form
Answer: \(B+M\) with \(B\subseteq\mathbb Q^m\) finite and \(M\) a \(V\)-vector lattice.
Page: 050
Chapter: 9
Section: 2
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\)
\(P\) a semi-\(V\)-affine lattice.
Index: 12
Kind: Lemma

Name: The group of invariant of \(X\)
Definition: The group of vectors \(v\in\mathbb Q^m\) such that \(X-v=X\).
Page: 051
Section: 9.2
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Q^m\).
Notation: inv(\(X\))

Page: 051
Section: 2
Notation: The \(V\)-vector lattice of invariant of \(M+B\)
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\),
\(M\) be a \(V\)-vector lattice,
\(B\subseteq\mathbb Q^m\) be a finite set.
Chapter: 9
Name: \(P\)
Example: Let \(b_0\in B\) arbitrary,
The \(V\)-vector lattice \(M'\) generated by \(M\) and the vectors \(v\in B-b_0\) such that \(v+B+M=B+M\)
Kind: Proposition
Index: 15

Name: A \(V\)-pattern
Definition: A \(V\)-affine lattice included in \(\mathbb Z^m\).
Page: 052
Section: 9.3
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space.

Name: A semi-\(V\)-pattern
Definition: A finite union of \(V\)-pattern.
Page: 052
Section: 9.3
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space
\(X\subseteq\mathbb Q^m\)

Definition: \(\mathbb Z^m\cap V\cap inv(P)\).
Page: 052
Section: 9.3
Variables: \(m\in\mathbb N\), \(V\subseteq\mathbb Q^m\) a vector space and \(P\subseteq\mathbb Q^m\) a semi-\(V\)-pattern.
Notation: \(\text{inv}_V(P)\)

Name: An additive group of \(\mathbb Q^m\)
Definition: A set \(M\subseteq \mathbb Q^m\) such that \(-M\subseteq M\) and \(M+M\subseteq M\).
Page: 038
Section: 8.3
Variables: \(m\in\mathbb N\).

Question: The set of additive subgroups of \(\mathbb Q^m\) is closed under
Answer: arbitrary intersection.
Page: 038
Section: 8.3
Variables: \(m\in\mathbb N\).

Name: A vector space
Definition: A set \(M\subseteq \mathbb Q^m\), for some \(m\in\mathbb N\) such that \(\lambda M\subseteq M\) for all \(\lambda\in \mathbb Q\) and \(M+M\subseteq M\).
Page: 043
Chapter: 8

Name: A \(V\)-vector lattice
Definition: A vector lattice \(M\) such that \(\text{vec}(M)=V\).
Page: 040
Chapter: 8
Section: 3
Variables: \(m\in\mathbb N\)
\(V\subseteq \mathbb Q^m\) a vector space.

Question: \(\gamma^{-1}_{r,m,\sigma}(B+M)\) is
Answer: of the form \(B_\sigma+\gamma_{r,m,0}^{-|\sigma|}(M)\) with \(B_\sigma\subseteq \mathbb Z^m\), \(|B_\sigma|\le |B|\) computable in \(P\) time
Page: 053
Chapter: 9
Section: 3.1
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space
\(B\subseteq \mathbb Z^m\) finite
\(M\subseteq\mathbb Z^m\) a \(V\)-vector lattice
\(\sigma\in\Sigma_r^*\).
Index: 18
Kind: Proposition

Name: A semi-\(V\)-pattern relatively prime with \(r\).
Definition: A semi-\(V\)-pattern \(P\) such that the \(V\)-lattice \(\text{inv}_V(P)\) is relatively prime with \(r\),
Page: 053, 54
Chapter: 9
Section: 3.2
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space.
Index: 19
Kind: Lemma
Definition2: \(B+M\) with \(B\subseteq\mathbb Z^m\) finite and \(M\) a \(V\)-lattice relatively prime with \(r\).

Name: The class of semi-\(V\)-pattern
Page: 053
Section: 3.2
Chapter: 9
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space.
Under: boolean combination
Under2: inverse gamma
Condition2: ?
Condition3: intersection

Question: The class of semi-\(V\)-pattern relatively prive with \(r\) included into a \(V\)-affine space is closed under
Answer: \(\gamma_{r,m,\sigma}^{-1}\) for all \(\sigma\in\Sigma_{r,m}^*\).
Page: 054
Chapter: 9
Section: 3.2
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space.
Index: 21
Kind: Proposition
Extra: complementing ? intersection ?

Question: There exists \(k\in\mathbb N\) such that for all \(\sigma\in\Sigma_{r,m}^{\ge k}\), \(\gamma_{r,m,\sigma}^{-1}(P)\) is
Answer: a semi-\(V\)-pattern
Page: 054
Chapter: 9
Section: 3.2
Variables: \(m,r\in\mathbb N\), let \(V\subseteq\mathbb Q^m\). Let \(P\) a semi-\(V\)-pattern.
Answer2: relatively prime with \(r\) and
Index: 21
Kind: Proposition
Answer3: included into a \(V\)-affine space.

Name: \(V\)-affine space
Definition: \(V+a\) for some \(a\in\mathbb Q^m\).
Page: 038
Chapter: 8
Section: 2
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space.

Name: An affine space
Definition: A \(V\)-affine space for some vector space \(V\subseteq\mathbb Q^m\).
Page: 038
Chapter: 8
Section: 2
Variables: \(m\in\mathbb N\).

Name: \(V\)-degenerate set
Definition: A set \(X\) such that \(V\) is not included in \(\overrightarrow{\text{saff} }(\mathbb Z^m\cap X)\).
Page: 057
Chapter: 10
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space.

Definition: \(X_1\Delta X_2\) is \(V\)-degenerate.
Page: 057
Variables: \(m\in\mathbb N\), let \(V\subseteq\mathbb Q^m\) a vector space, \(X_1,X_2\subseteq\mathbb Q^m\).
Notation: \(X_1\sim^V X_2\)
Index: 1
Kind: Lemma
Typ: an equivalence relation.

\(X\mapsto [X]^V\):
-commutes with boolean operations
-commutes with \(\gamma^{-1}_{r,m,\sigma}\).
Page: 057 58
Section: 10
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space
Index: 2 3 4
Kind: Lemma

Definition: \([X_1\#X_2]^V\).
Page: 057
Chapter: 10
Variables: \(m\in\mathbb N\),
let \(V\subseteq\mathbb Q^m\) a vector space,
\(X_1,X_2\subseteq\mathbb Q^m\)
\(\#\in\{\cup,\cap,\setminus,\Delta\}\).
Notation: \(X_1\#^VX_2\)

Name: The class of semi-\(V\)-affine lattices
Page: 050, 53
Section: 9.2, 9.3.1
Index: 18
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space.
Kind: Cor, Prop
Under: boolean combinations
Under2: \(\gamma_{r,m,\sigma}^{-1}\)
Under3: intersection
Condition3: infinite ?

Name: A \(V\)-hyperplane
Definition: A set of the form \(\{x\in V;\langle \alpha,x\rangle =c\}\) where \((\alpha,c)\in (V\setminus \{\mathbf E_{0,m}\})\times\mathbb Q\).
Page: 059
Section: 11.1
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(X\subseteq\mathbb Q^m\).
Extra: Plusieurs équivalences

Name: A \(V\)-half spaces
Definition: \(\{x\in V;\langle \alpha,x\rangle <c\}\) where \((\alpha,c)\in (V\setminus \{\mathbf E_{0,m}\})\times\mathbb Q\).
Page: 059
Section: 11.1
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(X\subseteq\mathbb Q^m\).

Name: An orientation
Definition: a function that associate to any couple \((V,H)\) where \(H\) is a \(V\)-hyperplane, one of those two open \(V\)-half spaces
Page: 060
Section: 11.1
Notation: \(o\)

Definition: \(o(V,H)\).
Page: 060
Section: 11.1
Variables: \(o\) an implicit orientation.
Notation: \((V,H)^>\)

Definition: \((V\setminus H)\setminus o(V,H)\).
Page: 060
Section: 11.1
Variables: \(o\) an implicit orientation.
Notation: \((V,H)^<\)

Definition: \(H\).
Page: 060
Section: 11.1
Variables: \(o\) an implicit orientation.
Notation: \((V,H)^=\)

Definition: \(o(V,H)\cup H\).
Page: 060
Section: 11.1
Variables: \(o\) an implicit orientation.
Notation: \((V,H)^\ge\)

Definition: \(H\cup (V,H)^<\).
Page: 060
Section: 11.1
Variables: \(o\) an implicit orientation.
Notation: \((V,H)^\le\)

Page: 060
Section: 11.1
Variables: \(V\subseteq\mathbb Q^m\) a vector space, \(H\subseteq \mathbb Q^m\) a \(V\)-hyperplane.
Notation: \(\vec H\)
Typ: A \(V\)-hyperplane

Name: An uniform orientation
Definition: An orientation function such that the direction of \(o(V,H)\) only depends of \(\vec H\).
Page: 060
Section: 11.1
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(o\) an orientation.

Name: A polyhedron
Definition: A boolean combination of \(H^{\#}\) where \(H\) is a \(\mathbb Q^m\) hyperplane and \(\#\in\{\le,<,=,>,\ge\}\).
Page: 060
Section: 11.2
Variables: \(X\subseteq\mathbb Q^m\)
\(o\) an implicit orientation

Name: A \(V\)-polyhedron
Definition: A polyhedron included in \(V\).
Page: 60
Section: 11.2
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(X\subseteq \mathbb Q^m\).
Definition2: A \((V,\mathcal H)\)-definable polyhedron for some finite set \(\mathcal H\) of \(V\)-hyperplane

Name: A \((V,\mathcal H)\)-definable \(V\)-polyhedron
Definition: A boolean combination in \(V\) of sets in \(\{H^\#;(H,\#)\in \mathcal H\times\{\le,<,=,>,\ge\}\}\).p
Page: 060
Section: 11.2
Variables: \(V\subseteq\mathbb Q^m\), \(\mathcal H\) a finite set of \(V\)-hyperplane and \(P\subseteq \mathbb Q^m\) a \(V\)-polyhedron. Let \(o\) an implicit orientation.

Name: A \(V\)-polyhedra equivalence class
Definition: The equivalence class for \(\sim ^V\) of a \(V\)-polyhedron.
Page: 061
Section: 11.2
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(\mathcal C\) a set of subset of \(\mathbb Q^m\).
Index: 3
Kind: Def

Name: Open convex in \(V\)
Definition: A finite intersection of open \(V\)-half spaces.
Page: 061
Section: 11.3
Variables: \(V\subseteq\mathbb Q^m\) a vector space and \(P\) a \(V\)-polyhedron.

Definition: \(\bigcap_{H\in\mathcal H} H^{\#H}\)
Page: 061
Section: 11.3
Variables: \(V\subseteq\mathbb Q^m\) a vector space,
\(P\) a \(V\)-polyhedron.
\(\mathcal H\) a finite set of \(V\)-hyperplane,
\(\#\in\{<,>\}^{\mathcal H}\).
\(o\) an implicit orientation.
Notation: \(C_{V,\#}\)

Question: \(C\setminus\bigcup_{H\in\mathcal H}H\) is to be a union of
Answer: finitely many open convex polyhedrons \(C_{V,\#}\), where \(\#\in\{<,>\}^{\mathcal H}\)
Page: 061
Section: 11.3
Variables: \(V\subseteq\mathbb Q^m\) a vector space,
\(\mathcal H\) a finite set of \(V\)-hyperplane.
\(C\) a \((V,\mathcal H)\)-definable polyhedron.
\(o\) an implicit orientation.

Definition: \(=H+(V,\overrightarrow H)^\#\)
Page: 60
Section: 11.1
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb Q^m\) a vector space,
\(H\) a \(V\)-hyperplane,
\(\#\in\{\le,<,=,>,\ge\}\) and
\(o\) an uniform orientation.
Notation: \((V,H)^\#\)

Name: A possible \(V\)-boundary of \(\mathcal C\)
Definition: a finite set of \(V\)-hyperplanes \(\mathcal H\) such that there exists a \((V,\mathcal H)\)-definable polyhedron in \(\mathcal C\).
Page: 63
Section: 11.5
Variables: \(m\in\mathbb N\)
\(V\subseteq\mathbb N^m\) a vector space,
\(o\) an uniform orientation,
\(\mathcal C\) a \(V\)-polyhedron equivalence class.

Name: The \(V\)-boundary of \(\mathcal C\)
Definition: The finite class \(\overrightarrow{\mathcal H_V(\mathcal C)}\) such that for all \(H\in\mathcal H_V(\mathcal C)\) there exists an open convex \(V\)-polyhedron \(C_H\) such that \(C_H\cap H^<\) and \(C_H\cap H^>\) are not \(V\)-degenerate and such that \([C_H]^V\cap ^V\mathcal C\) is equal to one of those two equivalence classes.
Page: 65
Section: 11.5
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a subspace,
\(\mathcal C\) a \(V\)-polyhedral equivalence class, a set of \(V\)-hyperplanes.
\(o\) to be an uniform implicit orientation.
Notation: \(\text{bound}_V(\mathcal C)\)
Index: 13
Kind: Def
Extra: hvc ?
Typ: A possible \(V\)-boundary of \(\mathcal C\) included into the direction of any possible \(V\)-boundary of \(\mathcal C\)

Name: The orthogonal of \(X\)
Definition: The set of \(y\in\mathbb Q^m\) such that for all \(x\in X\), \(\langle y,x\rangle=0\).
Page: 38
Chapter: 8
Section: 2
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Q^m\).
Notation: \(X^\bot\)
Typ: A vector space

Question: \(\left(X^\bot\right)^\bot=\)
Answer: \(\text{vec}(X)\).
Page: 38
Chapter: 8
Section: 2
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Q^m\).

Name: The orthogonal projection over \(A\)
Definition: the function \(f\) such as
 \(f(x)-x\in\left(\overrightarrow A\right)^\bot\).
Page: 38
Chapter: 8
Section: 2
Variables: \(m\in\mathbb N\), \(A\subseteq\mathbb Q^m\) non-empty affine.
Notation: \(\Pi_A\)
Typ: Affine function

Question: \(\gamma^{-1}_{r,m,\sigma}(\mathcal C+V^\bot)=\)
Answer: \(\mathcal C+V^\bot\).
Page: 67
Chapter: 11
Section: 6
Variables: \(r,m\in\mathbb N\), \(V\subseteq\mathbb Q^m\) a vector space,
\(\mathcal C\) a \(V\)-polyhedrons equivalence class and
\(\sigma\in\Sigma_{r,m}^*\).
Index: 18
Kind: Cor

Question: \(\overrightarrow{\text{saff} }(X_V )=\)
Answer: \(\{V\} \).
Page: 69
Chapter: 12
Variables: \(r,m\in\mathbb N\)
\(X\subseteq\mathbb Q^m\),
\(V\in \text{comp}\left(\overrightarrow{\text{saff} } (X)\right)\).

Name: A \(V\)-polyhedral partition of \(V\)
Definition: a non-empty finite sequence of \(V\)-polyhedral equivalence classes \(\left(\mathcal C_i\right)\) such that \(\mathcal C_i\cap\mathcal  C_j\) is \(V\)-degenerate for \(i\ne j\in I\) and \(\bigcup^V_{i\in I}\mathcal C_i=[V]^V\)
Page: 70
Chapter: 12
Variables: \(m\in\mathbb N\), \(V\subseteq\mathbb Q^m\)
Index: 3
Kind: Def

Smaller0: \(X\) is Presburger-definable
Greater0: \[\bigcup^V_{P\in\mathcal{P}_V(X)}\left([P]^V\cap^V (\mathcal C_{V,P}(X)+V^\bot)\right)\] where \(\mathcal P_V(X)\) is a non-empty finite class of semi-\(V\)-patterns and \(\left(\mathcal C_{V,P}(X)\right)_{P\in\mathcal P_V(X)}\) is a \(V\)-polyhedral partition.
Page: 70
Chapter: 12
Variables: \(m\in\mathbb N\)
\(X\subseteq\mathbb Z^m\)
\(V\in\overrightarrow{\text{saff} }(X)\).
Index: 4
Kind: Theo
Hide middle: yes
Prefix Greater: \([X_V]^V\) can be uniquely written as
Name: Decomposition theorem

Question: \([X_V]^V=\)
Answer: \([X]^V\)
Page: 72
Chapter: 12
Variables: \(m\in\mathbb N\),
\(X\subseteq\mathbb Z^m\)
\(V\in\overrightarrow{\text{saff} }(X)\).
Index: 4
Kind: Prop 6

Name: A component of \(G\)
Definition: A strongly connected component of the parallelization \([G]\).
Page: 77
Chapter: 13
Variables: \(G\) a FDVG

Name: Untransiant component of \(G\)
Definition: A component \(T\) such that there exists a loop \(q\overset{\sigma}\rightarrow{}q\) with \(q\in T\).
Page: 77
Chapter: 13
Section: 1
Variables: \(G\) a FDVG and \(T\) a component of \(G\)

Name: A transiant component
Definition: A component which is not untransiant.
Page: 77
Chapter: 13
Section: 1
Variables: \(G\) a FDVG and \(T\) a component of \(G\).

Name: The projection to \(A\)
Definition: \(f(x)=\left(1-\sum_{i=1}^mx[i]\right)f(\mathbf{e}_{0,m})+\sum_{i=1}^mx[i].f(\mathbf{e}_{i,m})\)
Page: 38
Chapter: 2
Section: 8
Variables: \(m\in\mathbb N\), \(A\subseteq\mathbb Q^m\) non-empty affine and \(f:\mathbb Q ^m\to\mathbb Q^m\).
Notation: \(\Pi_A\)
Definition2: \(f(x)=f(\mathbf{e}_{0,m}) +\sum_{i=1}^m x[i](f(\mathbf{e}_{i,m})-f(\mathbf{e}_{0,m}))\)
Conjdef: A function \(f\) which satisfies equivalently

Question: The sequence \(\left(\text{saff}\left(\{\xi_{r,m}\mid q\overset{w\in\Sigma^+_{r,m} }{\rightarrow}q\}\right)\right)_{q\in T}\) is uniquely decomposed as:
Answer: \(a_G(q)+V_G(T)\) with the \(a_G(q)\in V^\bot\) and \(V_G(T)\) a vector space.
Page: 79
Chapter: 13
Section: 1
Variables: \(G\) a finite graph labelled by \(\Sigma_{r,m}\), \(T\) an untransient component of \(G\).
Index: 3
Kind: Prop

Question: \(V_G(T)\) is computable in
Answer: P.
Page: 79
Chapter: 13
Section: 1.1
Variables: \(G\) a FDVG, \(T\) an untransient component of \(G\).
Index: 4
Kind: Theo

Page: 83
Section: 2
Notation: a partition \(B_0,B_1,\dots,B_n\) of \(B\) for all \(B'\subseteq B\), equivalently:
-\(M+B'\) is represented by some \(\mathcal A^F\)
-\(B'=\bigcup_{J}B_i\) for some \(J\subseteq\{1,\dots,n\}\).
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space,
\(M\subseteq\mathbb Z^m\) a \(V\)-vector lattice.
Let \(\mathcal A\) a FDVA,
\(B\subseteq\mathbb Z^m\) non-empty finite.
Chapter: 3
Name: P
Kind: Theo
Index: 12
Extra: todo

Definition: \(\{\gamma^{-1}_{r,m,w}(X)\mid w\in\Sigma^*_{r,m}\}\)
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Z^m\).
Notation: \(Q_{r,m}(X)\)

Definition: \(\{\gamma^{-1}_{r,m,w}(X)\mid w\in\Sigma^*_{r}\}\)
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\), \(X\subseteq\mathbb Z^m\).
Notation: \(K_{r,m}(X)\)

Definition: \((X,b)\mapsto\gamma^{-1}_{r,m,b}(X)\)
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\)
Notation: \(\delta_{r,m}\)

Definition: \((Q_{r,m}(X),m,K_{r,m}(X),\Sigma_r,\delta_{r,m})\)
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\) and \(X\subseteq\mathbb Z^m\)
Notation: \(G_{r,m}(X)\)

Definition: \(\mathbb Z^m\to\mathcal P(S_{r,m})\), \(Y\mapsto S_{r,m}\cap(1-r).Y\)
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\)
Notation: \(F_{r,m}\)

Definition: \(\left(X,G_{r,m}(X),F_{r,m}\right)\).
Page: 12
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\) and \(X\subseteq\mathbb Z^m\)
Notation: \(\mathcal A_{r,m}(X)\)
Applied to3: Represents \(X\)

Name: An empty component of \(\mathcal A\)
Definition: A component \(T\) such that, for all \(q\in T\), \([F_0](q)=\emptyset\).
Page: 84
Chapter: 13
Section: 3
Variables: \(\mathcal A=(q_0,G,F_0)\) a FDVA and \(T\) a component of \(\mathcal A\).
Extra: Not in the paper. Introduced to simplify definition of terminal

Definition: The set of terminal components of \(\mathcal A\).
Page: 84
Chapter: 13
Section: 3
Variables: \(\mathcal A=(q_0,G,F_0)\) a FDVA.
Notation: \(\mathcal{T}_{\mathcal A}\)

Smaller0: \(\gamma^{-1}_{r,m,\sigma^k}(\mathbb Z^m\cap A)\) is empty for some \(k\in\mathbb N\)
Greater0: \(\mathbb Z^m\cap A\) is empty
Page: 84
Chapter: 13
Section: 3
Variables: \(\sigma\in\Sigma^+_{r,m}\),
\(A\) affine.
Index: 14
Kind: Lem
Smaller to greater: iff
Hide middle: yes
Name: Destruction Lemma
Greater1: \(\xi_{r,m}(\sigma)\not\in A\)
Connect Greater0: or

Definition: The set of sequences \(\#\in\{<,>\}^{\text{bound}_V(X) }\) such that \([C_{V,\#}]^V\subseteq ^V\mathcal C_{V,P}(X)\).
Page: 86
Chapter: 13
Section: 3
Variables: \(X\) Presburger-definable
\(V\) an affine component of \(\overrightarrow{\text{saff}}(X)\)
\(P\in\mathcal P_V(X)\) a semi-\(V\)-pattern
\(o\) to be an uniform implicit orientation.
Notation: \(\mathcal S_{V,P}(X)\)

Name: Family of sets whose semi-affine spaces are exponential in the size of its minimal automaton
Page: 89
Chapter: 14
Section: 1
Kind: Lem
Example: \(\{0,\dots,r^n-1\}^m\)

Question: The semi affine hull of \(X\) is computable in
Answer: Exponential time.
Page: 89
Chapter: 14
Section: 1
Variables: \(X\) represented by a FDVA
Index: 2
Kind: Rem

Definition: The class of distinct patterns occurring in the decomposition of \([X_V]^V\).
Page: 70
Chapter: 12
Variables: \(m\in\mathbb N\), \(X\in\mathbb Z^m\) Presburger definable, \(V\in\text{comp}\left(\overrightarrow{\text{saff}}(X)\right)\).
Notation: \(\mathcal P_V(X)\)
Index: 4
Kind: Theo

Definition: The \(V\)-polyhedral equivalence class where the pattern \(P\) occur.
Page: 70
Chapter: 12
Variables: \(m\in\mathbb N\),
\(X\subseteq\mathbb Z^m\) Presburger definable,
\(V\in\text{comp}\left(\overrightarrow{\text{saff}}(X)\right)\) and
\(P\in\mathcal P_V(X)\).
Notation: \(\mathcal C_{V,P}(X)\)
Index: 4
Kind: Theo

Definition: \(\bigcap_{P\in\mathcal{P_V}(X)}\text{inv}_V(P)\).
Page: 91
Chapter: 12
Section: 2
Variables: \(m\in\mathbb N\),
\(X\subseteq\mathbb Z^n\) Presburger definable
\(V\in\text{comp}\left(\overrightarrow{\text{saff}}(X)\right)\).
Notation: \(\text{inv}_V(X)\)

Definition: \(\overrightarrow {\text{saff} }\left(\{\xi_{r,m}\mid q\overset{w\in\Sigma^+_{r,m} }{\rightarrow}q\}\right)\) for any \(q\in T\)
Page: 79
Chapter: 13
Section: 1.1
Variables: \(G\) a DVG,
\(T\) an untransiant component of \(G\).
Notation: \(V_G(T)\)
Index: 3
Kind: Prop

Definition: The element of \(A\cap (\vec A)^\bot\), for \(A=\text{saff} \left(\{\xi_{r,m}\mid q\overset{w\in\Sigma^+_{r,m} }{\rightarrow}q\}\right)\).
Page: 79
Chapter: 13
Section: 1.1
Variables: \(G\) a DVG, \(T\) an untransiant component of \(G\) and \(q\in T\).
Notation: \(a_G(q)\)
Index: 3
Kind: Prop

Name: The size of \(F\)
Definition: \(|Q|+|K|\).
Page: 011
Section: 3.2
Variables: \(F=(Q,f,m,K,S_r,\delta,K_F)\) a (finite) final function.
Index: 5
Kind: Def

Name: Its paralellization
Definition: \(Q\to\mathcal P(S_{r,m})\) is the language recognized by the automaton \((f(q),K,S_r,\delta,K_F)\).
Page: 011
Section: 3.2
Variables: \(F=(Q,f,m,K,S_r,\delta,K_F)\) a (finite) final function.
Notation: \([F]\)
Index: 5
Kind: Def

Definition: The set of \(V\)-hyperplanes \(H\) such that there exists an open convex \(V\)-polyhedron \(C_H\) such that \(C_H\cap H^<\) and \(C_H\cap H^>\) are not \(V\)-degenerate and such that \([C_H]^V\cap ^V\mathcal C\) is equal to one of those two equivalence classes.
Page: 64
Chapter: 11
Section: 5
Variables: \(m\in\mathbb N\), \(V\subseteq \mathbb Q^m\) a subspace, \(\mathcal C\) a \(V\)-polyhedral equivalence class. Let \(o\) to be an uniform implicite orientation.
Notation: \(\mathcal H_V(\mathcal C)\)
Index: 12
Kind: Prop

If:
-\(X\) is \((r,m,w)\)-cyclic and Presburger-definable,
-\([Z_{r,m,s}\cap(\xi_{r,m}(s)+V)]^V\) is not \(V\)-degenerate
-\(\delta(q_0,\sigma_1)=\delta(q_0,\sigma_2)\) iff \((\gamma_{r,m,\sigma_1}^{-1}(P))_{P\in\mathcal{P}_V(X)}=(\gamma_{r,m,\sigma_2}^{-1}(P))_{P\in\mathcal{P}_V(X)}\) for any \(\sigma_1,\sigma_2\in\Sigma_{r,m}^*\)
-\(Q'\) is the set of state, reachable from \(q_0\), such that \((\emptyset)_{P\in\mathcal P_V(X)}\ne(\gamma_{r,m,\sigma}^{-1}(P))_{P\in\mathcal{P}_V(X)}\) iff \(q'\in Q'\) for any path \(q_0\to^\sigma q'\) with \(\sigma\in\Sigma_{r,m}^*\),
-\(n_0\) is relative prime with \(r\)
-\(|(\mathbb Z^m\cap V)/\text{inv}_V(X)|\) divides \(n_0\),
-\(r^n\equiv 1\mod n_0\)
-\(U\) is the set of pairs \((k,Z)=(\delta(q_0,\sigma_{(k,Z)}),|\sigma_{(k,Z)}|)\), with \(\sigma_{(k,Z)}\) in \(\Sigma_{r}^*\) satisfying: there exists \(\sigma'_{(k,Z)}\in\Sigma_r^*\), such that
--\(|\sigma_{(k,Z)}.\sigma'_{(k,Z)}|\) is a multiple of \(mn\) ,
--there exists an \(s\)-eye \(Y'\) such that \(\delta(k,\sigma'_u)\in\text{ker}_s(Y')\subseteq Q'\) and
-\(\sigma_{(q_0,0)}=\epsilon\)
then
\(inv_{V}(X)\) equals the vector lattice generated by \(n_0\mathbb Z^m\cap V\) and the vectors \(\rho_{r,m}(\sigma_{(k_1,Z_1)}.b.\sigma'_{(k_2,Z_2)},s)-\rho_{r,m}(\sigma_{(k_2,Z_2)}.\sigma'_{(k_2,Z_2)},s)\) where \(b\in \Sigma_r\), \((k_2,Z_2)=(\delta(k_1,b),Z_1+1)\)
Page: 93
Chapter: 14
Section: 2
Variables: -\(m\in\mathbb N\),
-\(X\subseteq \mathbb Q^m\),
-\(V\in\overrightarrow{\text{saff}}(X)\)
-\(G\) a FDVG,
-\(o\) to be an uniform implicite orientation,
-\(s\in S_{r,m}\),
-\(w\in\Sigma_{r,m}^+\)
-\(q_0\) a principal state,
-\(Q'\) a set of principal states,
-\(n,n_0\in\mathbb N\setminus\{0\}\),
-\(U\subseteq K\times\mathbb Z/mn\mathbb Z\),
Index: 8
Kind: Prop
Extra: Preuve non comprise
sigma'_u ?
Q' vs K?
q_0 non initial ?

Name: Its initial state
Definition: \(q_0\)
Page: 12
Chapter: 7
Section: 3.2
Variables: \(\mathcal A=(q_0,G,F_0)\) an (F)DVA

Name: Its (finite) final function
Definition: \(F_0\)
Page: 12
Chapter: 7
Section: 3.2
Variables: \(\mathcal A=(q_0,G,F_0)\) an (F)DVA

Name: the convex hull of \(X\)
Definition: \(\left\{\sum_{i=1}^t \lambda_i x_i\mid t\ge1, x_1,\dots,x_t\in X; \lambda_1,\dots,\lambda_t\ge 0, \sum \lambda_i=1\right\}\)
Page: 6
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\), \(X\subseteq \mathbb Q^m\).
Abbreviation: conv.hull \(X\)
Applied to3: The smallest convex set containing \(X\)

Definition: The set of matrices with \(n\) rows and \(m\) columns with coefficient in \(X\).
Page: 005
Section: 2.2
Variables: \(X\subseteq \mathbb Q\)
\(m,n\in\mathbb N\)
Notation: \(\mathcal M_{m,n}(X)\)

Definition: A matrix with \(n\) rows and \(m\) columns with coefficient in \(X\)
Page: 5
Section: 2.2
Variables: \(X\subseteq \mathbb Q\)
\(i,j,m,n\in\mathbb N\)
Notation: \(M[i,j]\in X\)
Assuming: \(0< i\le m, 0<j\le n\)

Definition: The set of affine component of \(S\).
Page: 046
Section: 9.1.1
Variables: \(m\in\mathbb N\),
\(S\subseteq \mathbb Q^m\) a semi-affine space,
\(A\subseteq S\).
Notation: \(\text{comp}(S)\)

Smaller0: \(\gamma^{-1}_{r,m,\sigma}(A)\ne\emptyset\)
Greater0: a non-empty semi-\(\Gamma_{r,m,0}^{-|\sigma|}(V)\)-pattern,
Page: 54
Chapter: 9
Section: 3.2
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space,
\(A\) a \(V\)-affine space,
\(P\subseteq A\) a semi-\(V\)-pattern relatively prime with \(r\),
\(\sigma\in\Sigma_{r,m}^*\).
Index: 23
Kind: Corollary
Hide middle: yes
Prefix Greater: \(\gamma^{-1}_{r,m,\sigma}(P)\) is
Name: Dense pattern corollary
Greater1: relatively prime with \(r\),
Context: Leroux
Greater2: included in \(\Gamma^{-1}_{r,m,\sigma}(A)\)

Name: An affine \(I\)-representation of \(A\)
Definition: A couple \((a,(v_i)_{i\in I})\) where \(a\) is a vector in \(A\) such that \(a_i=0\) for any \(i\in I\) and \((v_i)_{i\in I}\) is the \(I\)-vector representation of \(V\).
Page: 038
Section: 8.2
Variables: \(m\in\mathbb N\),
\(V\subseteq \mathbb Q^m\) a vector space,
\(A\) a \(V\)-affine space.
Typ: Exactly one
Assuming: \(I\) is a full rank set of indices of \(V\)

Question: \(P\cap\left(C+V^\bot\right)\) is
Answer: Presburger-definable
Page: 69
Chapter: 12
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space,
\(P\) a semi-\(V\)-pattern and
\(C\) a \(V\)-polyhedron.

Name: An Hermite \(I\)-representation \(B\) of a \(M\)
Definition: An Hermite matrix \(B\) of order \(d\) such that \[M=group\left\{\sum_{k=1}^d B[k,j]v_{i_k}; j\in\{1,\dots,d\}\right\}\]
where \(v_i\) is the vector \(I\)-representation of \(V\).
Page: 040
Section: 8.3.1
Variables: \(m\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector,
\(M\) a \(V\)-vector lattice,
\(I=\{i_1,\dots,i_d\}\) with \(i_j<i_{j+1}\) be a full rank set of indices of a vector space \(V\).

Question: \(\mathbb Z^m\cap(\xi_{r,m}(w)+V)\) is
Answer: \((r,m)\)-detectable in \(X\)
Page: 82
Chapter: 13
Section: 2
Variables: \(m\in\mathbb N\),
\(X\subseteq\mathbb Z^m\)
\((r,m,w)\)-cyclic
\(V\in\text{comp}({\text{saff} }(X))\).
Index: 11
Kind: Cor
Assuming: \(X\) is Presburger definable

Page: 41
Section: 8.3.2
Notation: \(\bigcap_{i=1}^nM_j\)
Variables: \(V\subseteq \mathbb Q^m\) vector space
\((M_{i})_{i=1}^n\) a finite sequence of \(V\)-vector lattices
Name: P
Example: Let \(v_{1,j},\dots,v_{d,j}\) a \(\mathbb Z\)-basis of \(M_j\),
Let \(W\) the set of \((x,z_1,\dots,z_n)\in Q^n\times\prod_{j=1}^n\mathbb Q^d\) such that \(x=\sum_{i=1}^dz_j.v_{i,j}\) for each \(j\).
\(W\) admits a basis of the form \((x_i,z_{i,1},\dots,z_{i,n})_{1\le i\le d}\), take \(x_1,\dots, x_d\)
Kind: Lem
Index: 8

Definition: \(b_i\)
Page: 9
Section: 3.1
Variables: \(m,r,k\in\mathbb N\)
\(\sigma=b_1\dots b_k\in\Sigma^*_{r,m}\)
Notation: \(\sigma[i]_m\)

Definition: \(r^{|\sigma|_m} \frac{s}{1-r}+\sum_{i=1}^{|\sigma|_m}r^{i-1}\sigma[i]_m\)
Page: 9, 10
Section: 3.1
Variables: \(m,r\in\mathbb N\) and \((\sigma,s)\in\Sigma_{r,m}^*\times S_{r,m}\)
Notation: \(\rho_{r,m}(\sigma,s)\)
Definition2: \(\gamma_{r,m,\sigma}\left(\frac{s}{1-r}\right)\)

Name: A final function saturated for a DVG \(G\)
Definition: compatible with \(G\)
Page: 12
Section: 3.2
Variables: \(G=(Q,m,K,\Sigma_r,\delta)\) a DVG,
Definition2: \([F](q)\cap\{s\}=[F](\delta(q,s))\cap \{s\}\) for any \(q\in Q\) and \(s\in S_{r,m}\)
Conjdef: A final function \(F\)

Definition: \(\gamma^{-1}_{r,m,w}(X_q)\)
Page: 15
Chapter: 4
Section: 4.1
Notation: \(X_{\delta(q,w)} \)
Index: 1
Kind: Proposition

Name: The equivalence relation
Definition: The relation on states \(q_1,q_2\in Q\), with \(\delta(q_1,s^*)\cap \delta(q_2,s^*)\ne\emptyset\).
Page: 20
Chapter: 4
Section: 2.2
Variables: \(G=(Q,m,K,\Sigma_r,\delta)\) a FDVG.
\(s\in S_{r,m}\).
Notation: \(\sim_s\)
Index: 5
Kind: Theore

Name: The equivalence relation
Definition: \(|\sigma|/m\)
Page: 9
Section: 3.1
Variables: \(m,r\in\mathbb N\).
Notation: \(|\sigma|_{m} \)

Definition: \(\bigcup_{k\in\mathbb N}\gamma^{-k}_{r,m,e_{0,m} }(M) \)
Page: 43
Chapter: 8
Section: 3.4
Variables: \(m,r\in\mathbb N\),
\(V\subseteq\mathbb Q^m\) a vector space and
\(M\) a \(V\)-vector-lattice.
Typ: relatively prime with \(r\).
Assuming: \(\gamma^{-\infty}_{r,m,e_{0,m} }(M)\)

Page: 52
Section: 2
Notation: Equality of semi lattices
Variables: \(r,m\in\mathbb N\),
\(B_i\) finite subset of \(\mathbb Q^m\)
\(M_i\) vector lattices
\(P_i=B_i+M_i\) with
Chapter: 9
Name: P
Example: Let \(S_i=\bigcup_{b\in B_i}(b+V)\)
Check whether:
Either both \(B_i\) are empty, or none
\(inv(P_i)\) are equal
the \(S_i\) are equal
\(A\) a \(V\)-affine space containing the \(S_i\)
take \(a_0\in A\)
[$]\lambda=\defFun{V}{\mathbb Q^d}{v}{\text{the unique $x\in\mathbb Q^d$ such that $0\le x[i]<1$ and such that there exists $k\in \mathbb Z^d$ satisfying $v=\sum_{i=1}^d(x+k)[i].v_i$}}[/$]
Check whether \(\lambda(B_1)=\lambda(B_2)\)
Kind: Cor
Index: 16

Page: 91
Section: 1
Notation: \(\text{saff}(X)\)
Variables: \(m\in\mathbb N\),
\(X\subseteq\mathbb Z^n\) represented by a FDVA \(\mathcal A\).
Chapter: 12
Name: P
Example: Theo 13.4 and 14.5
Kind: Theo
Index: 6
Context: \(X\) is Presburger-definable

Page: 46
Section: 1.1
Notation: \(\text{comp}(S)\)
Variables: \(m\in\mathbb N\),
\(S\subseteq \mathbb Q^m\) a semi-affine space,
\(A\subseteq S\).
Chapter: 9
Name: P
Extra: todo

Page: 4
Implementation: \(X=\bigcup_{C\in\mathcal C}C\)
[$]f:\defFun{X\times\mathcal C}{\text{Rat}(\mathcal C)}{(x,C)}{C\text{if $x\in C$, }X\Delta C\text{ otherwise}}[/$]
[$]K=\defFun{X}{\text{Rat}(\mathcal C)}{x}{\bigcap_{C\in\mathcal C}f(x,i)}[/$]
Either \(E=\bigcup_{e\in E}K(e)\), in which case, return this expression
Or return False
Section: 2.1
Effect: A Boolean formula over elements of \(\mathcal C\) which evaluates to \(E\). Or its non-existence
Variables: \(E\) a finite set.
\(\mathcal C\subseteq\mathcal P(\mathbb Z^m)\)
Time complexity: P
Kind: Lem
Assuming: \(\mathcal C\)'s set are finite
Space complexity: Size of the expression \(X\): [$]\order{\abs{C}}[/$],
Size of the expression \(f(x,i)\): [$]\abs{X}=\order{\abs{C}}[/$]
Size of \(K(x)\):[$]\order{\abs{C}}[/$]
Size of \(\bigcup_{e\in E}K(x)\):[$]\order{\abs{E}\abs{C}}[/$]

Name: The digit-set conversion
Definition: [$]\defFun{D^*}{A^*}{w}{\text{An element $w'$ such that $\pi(w)=\pi(w')$}}[/$]
Page: 12
Section: 3.3
Variables: \(\{0,\dots,p-1\}\subseteq D\subseteq\mathbb Z\setminus\{0\}\) finite
Notation: \(\mathcal X_D\)

Definition: \(\left[\left\lceil \frac{f+1}{p-q} \right\rceil-1,\left\lfloor\frac{e-p}{p-q}\right\rfloor+1\right]\) set of states
Page: 12
Section: 3.3
Variables: \(p>q>1\)
Let \(\{0,\dots,p-1\}\subseteq [f,e]\subseteq\mathbb Z\setminus\{0\}\) finite
Notation: \(\mathcal U_D\)
Definition2: \(D\times A\)
Conjdef: The transducer with
Definition3: \(E\) the set of \((z,(d,a),z')\) such that \(qz+d=pz'+a\)
Definition4: \(\{0\}\)
Typ: Sequential
Definition5: \(\omega\) the final function [$]\defFun{\mathbb Z}{\mathcal P(A^*)}{z}{\langle z\rangle_{\frac pq}\text{if $z\ge0$}, \emptyset\text{ otherwise}}[/$]
Applied to3: A finite transducer implementing \(\mathcal X_D\)

Name: Presburger definable sets
Page: 15
Section: 4.1
Index: 2
Kind: Theo
Under: changing the initial state (\(X_q\))

Definition: the final function sending \(q\) to \(\{s\}\) if \(q\in Y\) and to \(\emptyset\) otherwise.
Page: 020
Section: 4.2.2
Variables: FDVG \(G=(Q,m,K,\Sigma_r,\delta)\),
\(s\in S_{r,m}\)
\(Y\) an \(s\)-eye.
Notation: \(F_{s,Y}\)

Definition: [$]\defFun{\mathbb Q^m}{\mathbb Q^m}{(x[1],\dots,x[m])}{(x[1],\dots,x[m])}[/$]
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\)
\((\sigma,s)\in\Sigma_{r,m}^*\times S_{r,m}\)
Notation: \(\Gamma_{r,m,\epsilon}\)
Index: 4.1

Definition: [$]\defFun{\mathbb Q^m}{\mathbb Q^m}{(x[1],\dots,x[m])}{(\Gamma_{r,m,\sigma}(r.x[m]+\sigma', x[1],\dots,x[m-1])}[/$]
Page: 010
Section: 3.1
Variables: \(m,r\in\mathbb N\)
\(\sigma\in\Sigma_r\)
\(\sigma'\in\Sigma_{r,m}^*\)
Notation: \(\Gamma_{r,m,\sigma\sigma'}\)
Index: 4.1