Computer Science – Data Structures and Algorithms
Scientific paper
2010-12-06
Computer Science
Data Structures and Algorithms
Scientific paper
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.
Gardy Danièle
Ponty Yann
No associations
LandOfFree
Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-167585