DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science

Font Size:  Small  Medium  Large

The register function for lattice paths

Guy Louchard, Helmut Prodinger

Abstract


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.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional