Discrete Mathematics & Theoretical Computer Science |

- 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.

Source: HAL:hal-01194675v1

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]

This page has been seen 196 times.

This article's PDF has been downloaded 193 times.