A positional numeration system is given by a base and by a set of digits. The base is a real or complex number β such that |β| > 1, and the digit set A is a finite set of real or complex digits (including 0). In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that β is any real or complex number, and digits are real or complex. We show that if (β, A) satisfies the so-called (OL) Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base β and alphabet A of contiguous integers, the system (β, A) has the (OL) Property if #A > |β| . Provided that addition and subtraction are realizable in parallel in the system (β, A), our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base β = 3+√5/2 with alphabet A = {-1, 0, 1}; base β = 2i with alphabet A = {-2, -1, 0, 1, 2} (redundant Knuth numeration system); and base β = -3/2 + z√3/2 = -1 + ω, where ω = exp 2iπ/3 , with alphabet A = {0, ±1, ±ω, ±ω2} (redundant Eisenstein numeration system).

Multiplication of two numbers represented in base /spl beta/ is shown to be computable by an online algorithm when /spl beta/ is a negative integer, a positive noninteger real number, or a complex number of the form i/spl radic/r, where r is a positive integer.

It is shown that a function is computable by an on-the-fly algorithm processing data in the most significant digit first fashion with a finite number of registers if and only if it is computable by a right subsequential finite state machine processing deterministically data in the least significant digit first fashion. Some applications to complex radix number systems are given.

It is shown that a function is computable by an on-the-fly algorithm processing data in the most significant digit first fashion with a finite number of registers if and only if it is computable by a right subsequential finite state machine processing data in the less significant digit first fashion. Applications to the conversion of redundant into conventional representations and to canonical Booth recoding are given. The author also indicates some applications to negative or complex radix number systems.

Numeration systems, the bases of which are defined by a linear recurrence with integer coefficients, are considered. Conditions on the recurrence are given under which the function of normalization which transforms any representation of an integer into the normal one-obtained by the usual algorithm-can be realized by a finite automaton. Addition is a particular case of normalization. The same questions are discussed for the representation of real numbers in basis theta , where theta is a real number >1. In particular it is shown that, if theta is a Pisot number, then the normalization and the addition in basis theta are computable by a finite automaton.>

Fibonacci representations of integers provide some kinds of universal coding. It is proved that it is possible to add two integers written in the Fibonacci numeration system of order m by means of a finite-state automaton. The conversion from a Fibonacci representation to the standard binary representation cannot be realized by a finite-state automaton.