The register function for lattice paths

Guy Louchard; Helmut Prodinger

The register function for lattice paths

Guy Louchard ¹ Helmut Prodinger ²

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

Domaine :

Informatique [cs] / Mathématique discrète [cs.DM]

Mathématiques [math] / Systèmes dynamiques [math.DS]

Mathématiques [math] / Combinatoire [math.CO]

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

dmAI0107.pdf

Fichiers éditeurs autorisés sur une archive ouverte

The register function for lattice paths

Fichier

Identifiants

Collections

Citation

Exporter

Métriques

148

76

Contact

The register function for lattice paths

Fichier

Identifiants

Collections

Citation

Exporter

Partager

Métriques

148

76

Contact