[en] We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n integers (or more generally on the first n elements in a given language). This leads to the notion of amortized (or average) carry propagation when applying the successor function. The second question is a computational issue: estimating the number of operations (in classical terms of Turing machines complexity) required to compute the representations of the first n integers from the first one by applying n times the successor function. This leads to the notion of (amortized) complexity, i.e., the average amount of computations required to obtain the successor of an element.
Disciplines :
Mathematics Computer science
Author, co-author :
Berthé, Valérie
Frougny, Christiane
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Sakarovitch, Jacques
Language :
English
Title :
On the concrete complexity of the successor function