Article contents
On-line finite automata for addition in some numeration systems
Published online by Cambridge University Press: 15 August 2002
Abstract
We consider numeration systems where the
base is a negative integer, or a complex number which is a root of a
negative integer.
We give parallel algorithms for addition in these numeration systems,
from which we derive on-line algorithms realized by finite
automata. A general construction relating addition in base β
and addition in base βm is given.
Results on addition in base $\beta=\sqrt[m]{b}$, where b is a relative
integer, follow.
We also show that addition in base the golden ratio
is computable by an on-line finite automaton, but is not
parallelizable.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 33 , Issue 1 , January 1999 , pp. 79 - 101
- Copyright
- © EDP Sciences, 1999
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20161010045746714-0336:S0988375499001071:S0988375499001071_eqnU3.gif?pub-status=live)
- 11
- Cited by