Structured numbers. Properties of a hierarchy of operations on binary trees
type: Item
instance of: scholarly article
title: Structured numbers. Properties of a hierarchy of operations on binary trees
zbMATH Open document ID: 0898.68054
published in: Acta Informatica
publication date: 1998-08-10T00:00:00Z
review text: The product of two positive integers \(a\) and \(b\) can be defined as the sum of \(b\) factors each equal to \(a\). The \(b\)th exponent of \(a\), denoted by \(a\uparrow b\), can similarly be defined as the product of \(b\) factors each equal to \(a\). The process of getting new operations by repeating old ones ends with exponentiation because this last operation is not associative. For \[ \underbrace {a\uparrow a\uparrow a\uparrow \ldots \uparrow a}_{_b\text{factors}} \] to be well defined, both the number of factors, and the order in which the operations \(\uparrow\) are performed, have to be specified. A way of doing this is to ask the second operand to carry not only a quantitative information, the number of times \(a\) is repeated, but also a structured information, the order in which the operations \(\uparrow\) are performed. Binary trees are naturally designated object to convey such a structured information. In this paper, we introduce a hierarchy of operations on binary trees. The operations are obtained by successive repetition of one initial operation. The first three operations are generalizations of the operations of addition, multiplication and exponentiation for natural numbers. We show that our hierarchy satisfies a range of algebraic properties that generalize the usual properties for addition, multiplication and exponentiation of natural numbers, and we justify the use of binary trees as one representation of the notion of structured number.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1154581
zbMATH Keywords: binary trees
zbMATH Keywords: structured number
author: Vincent D. Blondel
MaRDI profile type: Publication
full work available at URL: s002360050113
OpenAlex ID: W4241880289
DOI: 10.1007/S002360050113
description: scientific article; zbMATH DE number 1154581