On unary nodes in tries

Abstract : The difference between ordinary tries and Patricia tries lies in the fact that all unary nodes are removed in the latter. Their average number is thus easily determined from earlier results on the size of tries/Patricia tries. In a well-known contention resolution algorithm, whose probabilistic model is essentially equivalent to tries, unary nodes correspond to repetitions, i.e., steps in the algorithm that do not resolve anything at all. In this paper, we take an individual's view on such repetitions: we consider the distribution of the number of repetitions a certain contender encounters in the course of the algorithm―-which is equivalent to the number of unary nodes on the path from the root to a random string in a trie. We encounter an example of a sequence of distributions that does not actually converge to a limit distribution, but rather oscillates around a (discrete) limit distribution.
Type de document :
Communication dans un congrès
Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.577-590, 2010, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185574
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 20 août 2015 - 16:32:35
Dernière modification le : mardi 7 mars 2017 - 15:07:50
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:47:36

Fichier

dmAM0140.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185574, version 1

Collections

Citation

Stephan Wagner. On unary nodes in tries. Drmota, Michael and Gittenberger, Bernhard. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), pp.577-590, 2010, DMTCS Proceedings. 〈hal-01185574〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

117