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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="in...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/3/122 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><mi mathvariant="double-struck">Z</mi><mo>[</mo><mi>x</mi><mo>]</mo></mrow></semantics></math></inline-formula> 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 <i>P</i>, there exists a finite transducer automaton executing the addition operation of polynomials in canonical representation of base <i>P</i>. Finally, we observed the size—i.e., the number of states—of such automata. |
|---|---|
| ISSN: | 1999-4893 |