Non-redundant random generation algorithms for weighted context-free languages

Andy Lorenz 1 Yann Ponty 2, 3, *
* Auteur correspondant
3 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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We address the non-redundant random generation of $k$ words of length $n$ in a context-free language. Additionally, we want to avoid a predefined set of words. We study a rejection-based approach, whose worst-case time complexity is shown to grow exponentially with $k$ for some specifications and in the limit case of a coupon collector. We propose two algorithms respectively based on the recursive method and on an unranking approach. We show how careful implementations of these algorithms allow for a non-redundant generation of $k$ words of length $n$ in $\mathcal{O}(k\cdot n\cdot \log{n})$ arithmetic operations, after a precomputation of $\Theta(n)$ numbers. The overall complexity is therefore dominated by the generation of $k$ words, and the non-redundancy comes at a negligible cost.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, Generation of Combinatorial Structures, 502, pp.177-194. <10.1016/j.tcs.2013.01.006>


https://hal.inria.fr/inria-00607745
Contributeur : Yann Ponty <>
Soumis le : jeudi 1 novembre 2012 - 11:20:57
Dernière modification le : vendredi 13 septembre 2013 - 21:49:17
Document(s) archivé(s) le : samedi 2 février 2013 - 03:39:41

Fichiers

NonRedundantGeneration-TCS-201...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Andy Lorenz, Yann Ponty. Non-redundant random generation algorithms for weighted context-free languages. Theoretical Computer Science, Elsevier, 2013, Generation of Combinatorial Structures, 502, pp.177-194. <10.1016/j.tcs.2013.01.006>. <inria-00607745v2>

Exporter

Partager

Métriques

Consultations de
la notice

281

Téléchargements du document

182