You are here:
| 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 | |||
| http://hdl.handle.net/2268/15860 | |||
| On the cost and complexity of the successor function | |
| English | |
| Berthé, Valérie [ > > ] | |
| Frougny, Christiane [ > > ] | |
Rigo, Michel  [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):
| ||||||||||||||
All documents in ORBi are protected by a user license.
