Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.27
URN: urn:nbn:de:0030-drops-89204
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8920/
Heuberger, Clemens ; Krenn, Daniel ; Prodinger, Helmut
Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus
| pdf-format: |
|
Abstract
The summatory function of a q-regular sequence in the sense of Allouche and Shallit is analysed asymptotically. The result is a sum of periodic fluctuations multiplied by a scaling factor. Each summand corresponds to an eigenvalues of absolute value larger than the joint spectral radius of the matrices of a linear representation of the sequence. The Fourier coefficients of the fluctuations are expressed in terms of residues of the corresponding Dirichlet generating function. A known pseudo Tauberian argument is extended in order to overcome convergence problems in Mellin-Perron summation. Two examples are discussed in more detail: The case of sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input and the number of odd entries in the rows of Pascal's rhombus.
BibTeX - Entry
@InProceedings{heuberger_et_al:LIPIcs:2018:8920,
author = {Clemens Heuberger and Daniel Krenn and Helmut Prodinger},
title = {{Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {27:1--27:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8920},
URN = {urn:nbn:de:0030-drops-89204},
doi = {10.4230/LIPIcs.AofA.2018.27},
annote = {Keywords: Regular sequence, Mellin-Perron summation, summatory function, transducer, Pascal's rhombus}
}
| Keywords: | Regular sequence, Mellin-Perron summation, summatory function, transducer, Pascal's rhombus | |
| Seminar: | 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 18.06.2018 |
