Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-18T02:51:16.158Z Has data issue: false hasContentIssue false

On-line finite automata for addition in some numeration systems

Published online by Cambridge University Press:  15 August 2002

Christiane Frougny*
Affiliation:
Université Paris VIII and L.I.A.F.A., Case 7014, 2 place Jussieu, 75251 Paris Cedex 05, France; Christiane.Frougny@liafa.jussieu.fr.
Get access

Abstract

We consider numeration systems where the base is anegative integer, or a complex number which is a root of anegative 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 ratiois computable by an on-line finite automaton, but is notparallelizable.

Information

Type
Research Article
Copyright
© EDP Sciences, 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable