HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

Algebraic aspects of B-regular series

Philippe Dumas 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : This paper concerns power series of an arithmetic nature that arise in the analysis of divide-and-conquer algorithms. Two key notions are studied : that of B-regular sequence and that of Malherian sequence with their associated power series. Firstly we emphasize the link between rational series over the alphabet {x0, x1,....,xB-1} and B-regular series. Secondly we extend the theorem of Christol, Kamae, Mendes France and Rauzy about automatic sequences and algebraic series to B-regular sequences and Malherian series. We develop here a construtive theory of B-regular and Malherian series. The examples show the ubiquitous character of B-regular series in the study of arithmetic functions related to number representation systems and divide-and-conquer algorithms.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074743
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:13:01 PM
Last modification on : Thursday, February 3, 2022 - 11:16:51 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 6:51:04 PM

Identifiers

  • HAL Id : inria-00074743, version 1

Collections

Citation

Philippe Dumas. Algebraic aspects of B-regular series. [Research Report] RR-1931, INRIA. 1993. ⟨inria-00074743⟩

Share

Metrics

Record views

49

Files downloads

73