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 [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 | ||||||||||||||

| ||||||||||||||

All documents in ORBi are protected by a user license.