Gaussian Distribution of Trie Depth for Strongly Tame Sources

DOI10.1017/S0963548314000741zbMath1371.68056OpenAlexW4300553753MaRDI QIDQ5364227

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

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

Related Items

The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace ⋮ Towards a Realistic Analysis of Some Popular Sorting Algorithms ⋮ Lochs-type theorems beyond positive entropy ⋮ Process convergence for the complexity of radix selection on Markov sources

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Mellin transforms and asymptotics: Finite differences and Rice's integrals
Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
On decay of correlations in Anosov flows
On convergence rates in the central limit theorems for combinatorial structures
Euclidean algorithms are Gaussian
Special issue: Average-case analysis of algorithms
Dynamical sources in information theory: Fundamental intervals and word prefixes
Dynamical sources in information theory: A general analysis of trie structures
Erratum to: Dynamical sources in information theory: Fundamental intervals and word prefixes
Size and path length of Patricia tries: Dynamical sources context
Information theory: Sources, Dirichlet series, and realistic analyses of data structures
On a functional equation arising in the analysis of a protocol for a multi-access broadcast channel
The Number of Symbol Comparisons in QuickSort and QuickSelect
Digital Search Trees Revisited
Prevalence of rapid mixing in hyperbolic 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
Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
Typical Depth of a Digital Search Tree built on a general source
Sur un Theoreme Spectral et son Application aux Noyaux Lipchitziens
Towards a Realistic Analysis of Some Popular Sorting Algorithms
The Ubiquitous Digital Tree
Fractal Geometry, Complex Dimensions and Zeta Functions
Average profile of the Lempel-Ziv parsing scheme for a Markovian source

This page was built for publication: Gaussian Distribution of Trie Depth for Strongly Tame Sources