inria-00607745, version 2

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

Andy Lorenz a1, Yann Ponty () b23

Theoretical Computer Science 502 (2013) 177-194

Résumé : 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.

• Domaine : Informatique/Informatique et langage
Informatique/Algorithme et structure de données
Informatique/Mathématique discrète
• Mots-clés : random generation – recursive method – weighted context-free grammars
• Versions disponibles :  v1 (11-07-2011) v2 (01-11-2012)

• inria-00607745, version 2
• oai:hal.inria.fr:inria-00607745
• Contributeur :
• Soumis le : Jeudi 1 Novembre 2012, 11:20:57
• Dernière modification le : Vendredi 13 Septembre 2013, 21:49:17