s'authentifier
version française rss feed

inria-00607745, version 2

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

Andy Lorenz a1, Yann Ponty (Auteur à contacter de préférence) 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
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...