Digital trees and memoryless sources: from arithmetics to analysis

zbMATH Open1355.68062MaRDI QIDQ2959908FDOQ2959908

Authors: Mathieu Roux, Brigitte Vallée, Philippe Flajolet 

Publication date: 10 February 2017

Full work available at URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0117

Recommendations

• Dynamical sources in information theory: A general analysis of trie structures
• The Ubiquitous Digital Tree
• Towards a complete characterization of tries
• Typical depth of a digital search tree built on a general source
• Size and path length of Patricia tries: Dynamical sources context

zbMATH Keywords

Mellin transformanalysis of algorithmstriedigital treememoryless sourcescomplex asymptotics

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Cited In (21)

• The total path length of split trees
• A general central limit theorem for shape parameters of \(m\)-ary tries and PATRICIA tries
• A new binomial recurrence arising in a graphical compression algorithm
• Context trees, variable length Markov chains and dynamical sources
• Calculation of precise constants in a probability model of Zipf's law generation and asymptotics of sums of multinomial coefficients
• On time-space efficiency of digital trees with adaptive multidigit branching
• On 2-protected nodes in random digital trees
• On a recurrence arising in graph compression
• Central limit theorems for additive functionals and fringe trees in tries
• The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
• From coin tossing to rock-paper-scissors and beyond: a log-exp gap theorem for selecting a leader
• Inversions in split trees and conditional Galton-Watson trees
• The fluctuations of the giant cluster for percolation on random split trees
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• On the variety of shapes in digital trees
• Dynamical sources in information theory: A general analysis of trie structures
• Size and path length of Patricia tries: Dynamical sources context
• Zeta functions and solutions of Falconer-type problems for self-similar subsets of \(\mathbb{Z}^n\)
• Title not available (Why is that?)
• Asymptotic normality for the size of graph tries built from M-ary tree labelings

This page was built for publication: Digital trees and memoryless sources: from arithmetics to analysis

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