Geodesic
The Stack-Size of Combinatorial Tries Revisited
Discrete mathematics & theoretical computer science, Tome 5 (2002).

Voir la notice de l'article provenant de la source Episciences

In the present paper we consider a generalized class of extended binary trees in which leaves are distinguished in order to represent the location of a key within a trie of the same structure. We prove an exact asymptotic equivalent to the average stack-size of trees with α internal nodes and β leaves corresponding to keys; we assume that all trees with the same parameters α and β have the same probability. The assumption of that uniform model is motivated for example by the usage of tries for the compression of blockcodes. Furthermore, we will prove asymptotics for the r-th moments of the stack-size and we will show that a normalized stack-size possesses a theta distribution in the limit. 
@article{DMTCS_2002_5_a7,
     author = {Nebel, Markus E.},
     title = {The {Stack-Size} of {Combinatorial} {Tries} {Revisited}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {5},
     year = {2002},
     doi = {10.46298/dmtcs.301},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.301/}
}
TY  - JOUR
AU  - Nebel, Markus E.
TI  - The Stack-Size of Combinatorial Tries Revisited
JO  - Discrete mathematics & theoretical computer science
PY  - 2002
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.301/
DO  - 10.46298/dmtcs.301
LA  - en
ID  - DMTCS_2002_5_a7
ER  - 
%0 Journal Article
%A Nebel, Markus E.
%T The Stack-Size of Combinatorial Tries Revisited
%J Discrete mathematics & theoretical computer science
%D 2002
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.301/
%R 10.46298/dmtcs.301
%G en
%F DMTCS_2002_5_a7
Nebel, Markus E. The Stack-Size of Combinatorial Tries Revisited. Discrete mathematics & theoretical computer science, Tome 5 (2002). doi : 10.46298/dmtcs.301. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.301/

Cité par Sources :