Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

On the concrete complexity of the successor function ; ; Rigo, Michel et al Conference (2012, September 11) We consider two kinds of questions about the successor function. The ﬁrst one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n ... [more ▼] We consider two kinds of questions about the successor function. The ﬁrst 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. [less ▲] Detailed reference viewed: 86 (5 ULg)On the cost and complexity of the successor function ; ; Rigo, Michel et al in Arnoux, P.; Bédaride, N. (Eds.) Proceedings of WORDS 2007 (2007) For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word ... [more ▼] For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word of a genealogically ordered language L onto the (n+1)-th word of L. We show that, if the ratio of the number of elements of length n + 1 over the number of elements of length n of the language has a limit b> 1, then the amortized cost of the successor function is equal to b/(b − 1). From this, we deduce the value of the amortized cost for several classes of numeration systems (integer base systems, canonical numeration systems associated with a Parry number, abstract numeration systems built on a rational language, and rational base numeration systems). [less ▲] Detailed reference viewed: 15 (1 ULg) |
||