On-line finite automata for addition in some numeration systems
Christiane Frougny · RAIRO - Theoretical Informatics and Applications · 1999
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.