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

Title:
Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models
Authors:
Gardy, Danièle, Ponty, Yann
Contributors:
Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), Algorithms and Models for Integrative Biology (AMIB), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Centre Inria de Saclay, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS), LACIM, UQAM, ANR-07-BLAN-0330,GAMMA,Génération Aléatoire : Modèles, Méthodes et Algorithmes(2007)
Source:
GASCOM - 8th conference on random generation of combinatorial structures - 2010, LACIM, UQAM, Sep 2010, Montréal, Canada. 14pp
Publisher Information:
CCSD, 2010.
Publication Year:
2010
Collection:
collection:X
collection:EC-PARIS
collection:CNRS
collection:INRIA
collection:UNIV-PSUD
collection:LIX
collection:INRIA-SACLAY
collection:PRISM
collection:X-LIX
collection:X-DEP
collection:X-DEP-INFO
collection:INRIA_TEST
collection:TESTALAIN1
collection:UMR8623
collection:UVSQ
collection:INRIA2
collection:UNIV-PARIS-SACLAY
collection:UNIV-PSUD-SACLAY
collection:ANR
Subject Terms:
Coupon collector, Birthday paradox, Random generation, Context-free languages, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.1: Combinatorics, G.2.1.2: Generating functions, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, F.2.2.1: Computations on discrete structures, ACM: J.: Computer Applications, J.3: LIFE AND MEDICAL SCIENCES, J.3.0: Biology and genetics, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Subject Geographic:
Montréal, Canada
Original Identifier:
ARXIV: 1012.1129
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/1012.1129
Access URL:
https://inria.hal.science/inria-00543150
https://inria.hal.science/inria-00543150v1/document
https://inria.hal.science/inria-00543150v1/file/GASCOM-2010-Allocations.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00543150v1
Database:
HAL

Weitere Informationen

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.