Guy Louchard ; Helmut Prodinger - The register function for lattice paths

dmtcs:3560 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3560
The register function for lattice pathsArticle

Authors: Guy Louchard 1; Helmut Prodinger 2

  • 1 D├ępartement d'Informatique [Bruxelles]
  • 2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]

The register function for binary trees is the minimal number of extra registers required to evaluate the tree. This concept is also known as Horton-Strahler numbers. We extend this definition to lattice paths, built from steps $\pm 1$, without positivity restriction. Exact expressions are derived for appropriate generating functions. A procedure is presented how to get asymptotics of all moments, in an almost automatic way; this is based on an earlier paper of the authors.


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: Register function,Horton-Strahler numbers,Gumbel distribution,moments,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

References

Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 130 times.