# Automata and Arithmetics in Canonical Number Systems
## 3 Automata and Canonical Number Systems  
As we have seen before, adding and multiplying by a constant are implementable with automata in CNSs. In this section, we prove that an automaton exists that executes the digit-wise addition. The existence of such an automaton is not obvious since the length of the sum of two algebraic integers represented in the canonical number system may have a shorter length than the summands'. Definition 4: The 6-tuple \(\mathcal{A}=(k,S,X,Y,s,\delta)\) is called a finite transducer automaton with \(k\) input tape if  
\(k\in\mathbb{Z}^{+}\)_;_  
\(S\) _is a finite, non-empty set of states;_  
\(X\) _is a finite set of at least two elements (the input alphabet);_  
\(Y\) _is a finite set of at least two elements (the output alphabet);_  
\(s\in S\) _is the initial state;_  
\(\delta:S\times X^{k}\longrightarrow S\times Y\) _is a unique mapping._  
Remark 9: _We follow the convention for extending the transducer automaton to operate on words of the input alphabet and having the result as a word of the output alphabet._  
In the following, if \(\bar{a}=(a_{0}\ldots a_{n-1})\in\mathcal{N}^{*}\) is a finite word, then we will use the notation \(Q_{a}(x)=a_{n-1}x^{n-1}+\cdots+a_{0}\) for the corresponding polynomial. **Theorem 5**. : _Let \((P,\mathcal{N})\) be a CNS. Then, there exists a finite transducer automaton \(\mathcal{A}\) with two input tapes, such that \(\bar{c}=\mathcal{A}(\bar{a},\bar{b})\) for all \(\bar{a},\bar{b},\bar{c}\in\mathcal{N}^{*}\) if \(\varphi(Q_{c})=\varphi(Q_{a}+Q_{b})\)._  
**Remark 10**. : _In Theorem 5, we assume that the length of the words \(\bar{a},\bar{b},\bar{c}\) are equal. If not, we extend them with the necessary amount of \(0\)s on the right._  
**Remark 11**. : _In [19], there is a similar result, but the proof there is not constructive. Furthermore, based on our proof, we can state the minimality of our construction, as it is done in Theorem 6._  
Proof of Theorem 5.: We prove the statement by constructing the addition automaton \(\mathcal{A}=(2,S,X,Y,s,\delta)\), where \(X=Y=\mathcal{N}\). We will define \(S\subseteq\mathcal{N}[x]\) and \(\delta\) in an appropriate way, and we will prove that \(S\) is finite. Assume that \(N=|\mathcal{N}|\). Let \(S\) be the smallest set such that  
1. \(0\in S\);
2. if \(A\in S\), \(B\in\mathcal{N}[x]\), \(b\in\mathcal{N}\), and \(0\leq a<2N-1\) such that \(\varphi(xB(x)+b)=\varphi(A(x)+a)\) then \(B\in S\). We define the transition function \(\delta:S\times\mathcal{N}^{2}\longrightarrow S\times\mathcal{N}\) by \(\delta(A,a_{1},a_{2})=(B,b)\), if \(\varphi(xB(x)+b)=\varphi(A(x)+a_{1}+a_{2})\). Let \(\bar{a},\bar{b}\in\mathcal{N}^{*}\), \(A_{0}=0\), and \(Q_{0}=Q_{a}+Q_{b}\). If \(0\leq i\), let \(A_{i+1}\) be defined by \(\delta(A_{i},a_{i},b_{i})=(A_{i+1},c_{i})\), and \(Q_{i+1}(x)=Q_{i}(x)+(c_{i}-a_{i}-b_{i})x^{i}\). By the definition of \(\delta\), we have  
\[\varphi\Big{(}Q_{i+1}(x)+A_{i+1}(x)x^{i+1}\Big{)}=\varphi\Big{(}Q_{i}(x)+A_{i }(x)x^{i}\Big{)}=\varphi(Q_{a}+Q_{b})\;,\]  
for all \(0\leq i\). Let \(n=1+\max\{\deg(Q_{a}),\deg(Q_{b})\}\) and \(k=1+\deg(A_{i})\). Then, \(\deg(Q_{n})<n\), \(Q_{c}=Q_{n+k}=Q_{n}+A_{n}x^{n}\in\mathcal{N}[x]\), and \(\varphi(Q_{c})=\varphi(Q_{a}+Q_{b})\). Hence, by Theorem 4, and by Lemma 1(iii),  
\[n+k =\deg(Q_{c})+1=L(Q_{c})\] \[\leq\mathbb{I}(Q_{c})+C_{2}\] \[\leq\max\{\mathbb{I}(Q_{a}),\mathbb{I}(Q_{b})\}+\mathbb{I}(2)+C_ {2}\] \[=n+\mathbb{I}(2)+C_{2}\;,\]  
where \(C_{2}\) is the constant \(c_{2}\) in Theorem 4. This yields that  
\[\deg(A_{i})<k\leq\mathbb{I}(2)+C_{2}\;.\]  
Since \(S\) is defined to be the smallest set satisfying (1) and (2), every \(A\in S\) may appear as the last carry \(A_{n}\). Thus, for all \(A\in S\subseteq\mathcal{N}[x]\), \(\deg(A)<\mathbb{I}(2)+C_{2}\), which implies that \(S\) is finite. **Remark 12**. : _Observe now the properties of the states defined in the proof of Theorem 5. Let \(A(x)=a_{k}x^{k}+a_{k-1}x^{k-1}+\cdots+a_{0}\), where \(a_{k}\
eq 0\) and \(A(x)\in S\).