|Reference : On the cost and complexity of the successor function|
|Scientific congresses and symposiums : Paper published in a book|
|Engineering, computing & technology : Computer science|
Physical, chemical, mathematical & earth Sciences : Mathematics
|On the cost and complexity of the successor function|
|Berthé, Valérie [ > > ]|
|Frougny, Christiane [ > > ]|
|Rigo, Michel [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]|
|Sakarovitch, Jacques [ > > ]|
|Proceedings of WORDS 2007|
|[en] successor function ; complexity ; numeration system|
|[en] 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).
|File(s) associated to this reference|
All documents in ORBi are protected by a user license.