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 mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Sakarovitch, Jacques [ > > ]
Proceedings of WORDS 2007
Arnoux, P.
Bédaride, N.
[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

Fulltext file(s):

Restricted access
bfrs.pdfAuthor preprint167.13 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.