×

On the associativity of algorithms. (English) Zbl 0957.11007

Let \(\Lambda\) be the set of the strictly decreasing sequences \(\lambda=(\lambda_n)\) of positive real numbers for which \(L(\lambda):=\sum^\infty_{n=1}\lambda_n<+\infty\) and \(N\) be a fixed positive integer. A sequence \((\lambda_n)\in \Lambda\) is called interval filling of order \(N\) if, for any \(x\in [0,NL(\lambda)]\), there exists a sequence \((\delta_n)\) such that \(\delta_n\in\{0,1,\dots,N\}\) and \(x=\sum^\infty_{n=1}\delta_n\lambda_n\). An algorithm (with respect to \(\lambda=(\lambda_n))\) is defined as a sequence of functions \(\alpha_n:[0,NL(\lambda)]\to\{0,1,\dots,N\}\) for which \[ x=\sum^\infty_{n=1}\alpha_n(x)\lambda_n \qquad (x\in [0,L(\lambda)]). \] The algorithm \((\alpha_n)\) is called associative if the binary operation \(\circ\) on \([0,NL(\lambda)]\) defined by \[ x\circ y=\sum^\infty_{n=1} \min \{\alpha_n(x),\alpha_n(y)\}\lambda_n \] is associative. In the paper it is shown that the elements of a wide and important class of algorithms (the so-called regular algorithms) are associative and there are other associative algorithms, too. On the other hand there are important algorithms (e.g., the so-called quasi-regular and anti-regular algorithms) that are not associative.

MSC:

11A67 Other number representations
26A99 Functions of one variable