Search Results

Documents authored by Prodinger, Helmut

Document
DOI: 10.4230/LIPIcs.AofA.2018.26
Counting Ascents in Generalized Dyck Paths

Authors: Benjamin Hackl, Clemens Heuberger, 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
Non-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees. We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance.
Cite as

Benjamin Hackl, Clemens Heuberger, and Helmut Prodinger. Counting Ascents in Generalized Dyck Paths. 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. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hackl_et_al:LIPIcs.AofA.2018.26,
  author =	{Hackl, Benjamin and Heuberger, Clemens and Prodinger, Helmut},
  title =	{{Counting Ascents in Generalized Dyck Paths}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{26:1--26:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.26},
  URN =		{urn:nbn:de:0030-drops-89191},
  doi =		{10.4230/LIPIcs.AofA.2018.26},
  annote =	{Keywords: Lattice path, Lukasiewicz path, ascent, asymptotic analysis, implicit function, singular inversion}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.27
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.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}
}
Document
DOI: 10.4230/DagSemRep.185
`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728)

Authors: Philippe Flajolet, Rainer Kemp, Hosam M. Mahmoud, and Helmut Prodinger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, Hosam M. Mahmoud, and Helmut Prodinger. `Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728). Dagstuhl Seminar Report 185, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.185,
  author =	{Flajolet, Philippe and Kemp, Rainer and Mahmoud, Hosam M. and Prodinger, Helmut},
  title =	{{`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728)}},
  pages =	{1--23},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{185},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.185},
  URN =		{urn:nbn:de:0030-drops-150720},
  doi =		{10.4230/DagSemRep.185},
}
Document
DOI: 10.4230/DagSemRep.119
`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)

Authors: Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick. `Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527). Dagstuhl Seminar Report 119, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.119,
  author =	{Flajolet, Philippe and Kemp, Rainer and Prodinger, Helmut and Sedgewick, Robert},
  title =	{{`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{119},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.119},
  URN =		{urn:nbn:de:0030-drops-150079},
  doi =		{10.4230/DagSemRep.119},
}
Document
DOI: 10.4230/DagSemRep.68
"Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328)

Authors: Philippe Flajolet, Rainer Kemp, and Helmut Prodinger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, and Helmut Prodinger. "Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328). Dagstuhl Seminar Report 68, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.68,
  author =	{Flajolet, Philippe and Kemp, Rainer and Prodinger, Helmut},
  title =	{{"Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328)}},
  pages =	{1--32},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{68},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.68},
  URN =		{urn:nbn:de:0030-drops-149562},
  doi =		{10.4230/DagSemRep.68},
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact