On-line finite automata for addition in some numeration systems
Université Paris VIII and
L.I.A.F.A., Case 7014, 2 place Jussieu, 75251
Paris Cedex 05, France;
Accepted: November 1998
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 , 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.
© EDP Sciences, 1999