Reference : On the cost and complexity of the successor function
Scientific congresses and symposiums : Paper published in a book
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/15860
On the cost and complexity of the successor function
English
Berthé, Valérie [ > > ]
Frougny, Christiane [ > > ]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Sakarovitch, Jacques [ > > ]
2007
Proceedings of WORDS 2007
Arnoux, P.
Bédaride, N.
Yes
International
WORDS
Marseille
France
[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).
Researchers
http://hdl.handle.net/2268/15860

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
bfrs.pdfAuthor preprint167.13 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.