Gaussian distribution of trie depth for strongly tame sources

DOI10.1017/S0963548314000741MaRDI QIDQ5364227zbMATH OpenOpenAlexFDO

Authors Eda Cesaratto, Brigitte Vallée

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548314000741

Mathematics Subject Classification ID

Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Concentration of Size and Path Length of Tries
• Dynamical sources in information theory: A general analysis of trie structures
• Profiles of Tries
• A note on the asymptotic behavior of the depth of tries
• Profile of Tries

Cites work

• Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
• Average profile of the Lempel-Ziv parsing scheme for a Markovian source
• Digital Search Trees Revisited
• Dynamical sources in information theory: A general analysis of trie structures
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Erratum to: Dynamical sources in information theory: Fundamental intervals and word prefixes
• Euclidean algorithms are Gaussian
• Fractal Geometry, Complex Dimensions and Zeta Functions
• scientific article; zbMATH DE number 3978406 (Why is no real title available?)
• scientific article; zbMATH DE number 1187021 (Why is no real title available?)
• scientific article; zbMATH DE number 3678541 (Why is no real title available?)
• scientific article; zbMATH DE number 3622081 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1516956 (Why is no real title available?)
• scientific article; zbMATH DE number 1545683 (Why is no real title available?)
• scientific article; zbMATH DE number 1552278 (Why is no real title available?)
• Information theory: sources, Dirichlet series, and realistic analyses of data structures
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
• On convergence rates in the central limit theorems for combinatorial structures
• On decay of correlations in Anosov flows
• On the average redundancy rate of the Lempel-Ziv code
• Opérateurs de Ruelle-Mayer généralisés et analyse en moyenne des algorithmes d'Euclide et de Gauss
• Prevalence of rapid mixing in hyperbolic flows
• Size and path length of Patricia tries: Dynamical sources context
• Special issue: Average-case analysis of algorithms
• Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• The Ubiquitous Digital Tree
• Towards a realistic analysis of some popular sorting algorithms
• Typical depth of a digital search tree built on a general source

Cited in

(5)

• A study of trie-like structures under the density model
• Process convergence for the complexity of radix selection on Markov sources
• Lochs-type theorems beyond positive entropy
• The depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• Towards a realistic analysis of some popular sorting algorithms

This page was built for publication: Gaussian distribution of trie depth for strongly tame sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5364227)