Automata and Arithmetics in Canonical Number Systems

In this paper, we discuss canonical number systems (CNSs), which are generalizations of positional number systems to polynomials over the integers. We defined the information quantity of a polynomial A∈Z[x] relative to the base of the CNS and proved that it has a strong relation with the length of the representation in the number system. Based on this result, we showed that for every CNS polynomial P, there exists a finite transducer automaton executing the addition operation of polynomials in canonical representation of base P. Finally, we observed the size—i.e., the number of states—of such automata.