Geodesic
Digital Trees and Memoryless Sources: from Arithmetics to Analysis
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

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

Digital trees, also known as $\textit{"tries''}$, are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This extended abstract develops the asymptotic form of expectations of the main parameters of interest, such as tree size and path length. The analysis is conducted under the simplest of all probabilistic models; namely, the $\textit{memoryless source}$, under which letters that data items are comprised of are drawn independently from a fixed (finite) probability distribution. The precise asymptotic structure of the parameters' expectations is shown to depend on fine singular properties in the complex plane of a ubiquitous $\textit{Dirichlet series}$. Consequences include the characterization of a broad range of asymptotic regimes for error terms associated with trie parameters, as well as a classification that depends on specific $\textit{arithmetic properties}$, especially irrationality measures, of the sources under consideration. 
@article{DMTCS_2010_special_258_a35,
     author = {Flajolet, Philippe and Roux, Mathieu and Vall\'ee, Brigitte},
     title = {Digital {Trees} and {Memoryless} {Sources:} from {Arithmetics} to {Analysis}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2799},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2799/}
}
TY  - JOUR
AU  - Flajolet, Philippe
AU  - Roux, Mathieu
AU  - Vallée, Brigitte
TI  - Digital Trees and Memoryless Sources: from Arithmetics to Analysis
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2799/
DO  - 10.46298/dmtcs.2799
LA  - en
ID  - DMTCS_2010_special_258_a35
ER  - 
%0 Journal Article
%A Flajolet, Philippe
%A Roux, Mathieu
%A Vallée, Brigitte
%T Digital Trees and Memoryless Sources: from Arithmetics to Analysis
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2799/
%R 10.46298/dmtcs.2799
%G en
%F DMTCS_2010_special_258_a35
Flajolet, Philippe; Roux, Mathieu; Vallée, Brigitte. Digital Trees and Memoryless Sources: from Arithmetics to Analysis. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2799. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2799/

Cité par Sources :