Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models

Danièle Gardy 1 Yann Ponty 2, 3, *
* Auteur correspondant
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The present work analyzes the redundancy of sets of combinatorial objects produced by a weighted random generation algorithm proposed by Denise et al. This scheme associates weights to the terminals symbols of a weighted context-free grammar, extends this weight definition multiplicatively on words, and draws words of length $n$ with probability proportional their weight. We investigate the level of redundancy within a sample of $k$ word, the proportion of the total probability covered by $k$ words (coverage), the time (number of generations) of the first collision, and the time of the full collection. For these four questions, we use an analytic urn analogy to derive asymptotic estimates and/or polynomially computable exact forms. We illustrate these tools by an analysis of an RNA secondary structure statistical sampling algorithm introduced by Ding et al.
Type de document :
Communication dans un congrès
GASCOM - 8th conference on random generation of combinatorial structures - 2010, Sep 2010, Montréal, Canada. 14pp, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00543150
Contributeur : Yann Ponty <>
Soumis le : lundi 6 décembre 2010 - 09:25:47
Dernière modification le : jeudi 10 mai 2018 - 02:06:49
Document(s) archivé(s) le : lundi 7 mars 2011 - 02:31:33

Fichiers

GASCOM-2010-Allocations.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00543150, version 1
  • ARXIV : 1012.1129

Collections

Citation

Danièle Gardy, Yann Ponty. Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models. GASCOM - 8th conference on random generation of combinatorial structures - 2010, Sep 2010, Montréal, Canada. 14pp, 2010. 〈inria-00543150〉

Partager

Métriques

Consultations de la notice

398

Téléchargements de fichiers

149