The register function for lattice paths

Guy Louchard 1 Helmut Prodinger 2
1 ULB - Département d'Informatique [Bruxelles]
2 DMS - Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
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.
Keywords : Register function Horton-Strahler numbers Gumbel distribution moments
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.135-148, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01194675
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:58
Dernière modification le : mercredi 10 mai 2017 - 17:41:05
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:56:48

Fichier

dmAI0107.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194675, version 1

Collections

INSMI | TDS-MACS

Citation

Guy Louchard, Helmut Prodinger. The register function for lattice paths. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.135-148, 2008, DMTCS Proceedings. 〈hal-01194675〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

180

Contact


archive-ouverte@inria.fr