Paper published in a book (Scientific congresses and symposiums)
On the cost and complexity of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel et al.
2007In Arnoux, P.; Bédaride, N. (Eds.) Proceedings of WORDS 2007
Peer reviewed
 

Files


Full Text
bfrs.pdf
Author preprint (171.14 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
successor function; complexity; numeration system
Abstract :
[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).
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 cost and complexity of the successor function
Publication date :
2007
Event name :
WORDS
Event place :
Marseille, France
Audience :
International
Main work title :
Proceedings of WORDS 2007
Author, co-author :
Arnoux, P.
Bédaride, N.
Peer reviewed :
Peer reviewed
Available on ORBi :
since 01 July 2009

Statistics


Number of views
56 (1 by ULiège)
Number of downloads
0 (0 by ULiège)

Bibliography


Similar publications



Contact ORBi