Skip to Main content Skip to Navigation
Conference papers

The register function for lattice paths

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 $\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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01194675
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, September 7, 2015 - 12:50:58 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:37 PM
Long-term archiving on: : Tuesday, December 8, 2015 - 12:56:48 PM

File

dmAI0107.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Guy Louchard, Helmut Prodinger. The register function for lattice paths. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. pp.135-148, ⟨10.46298/dmtcs.3560⟩. ⟨hal-01194675⟩

Share

Metrics

Record views

83

Files downloads

318