1 Search Results for "Krenn, Daniel"


Document
Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus

Authors: Clemens Heuberger, Daniel Krenn, and Helmut Prodinger

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


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.

Cite as

Clemens Heuberger, Daniel Krenn, and Helmut Prodinger. Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{heuberger_et_al:LIPIcs.AofA.2018.27,
  author =	{Heuberger, Clemens and Krenn, Daniel and Prodinger, Helmut},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.27},
  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}
}
  • Refine by Author
  • 1 Heuberger, Clemens
  • 1 Krenn, Daniel
  • 1 Prodinger, Helmut

  • Refine by Classification
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Generating functions
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 Mellin-Perron summation
  • 1 Pascal's rhombus
  • 1 Regular sequence
  • 1 summatory function
  • 1 transducer

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail