Loading [MathJax]/jax/output/HTML-CSS/jax.js

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 pathsConference paper

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 ±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]

Consultation statistics

This page has been seen 236 times.
This article's PDF has been downloaded 239 times.