Non-redundant random generation algorithms for weighted context-free grammars
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 O(k . n . 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. (C) 2013 Elsevier B.V. All rights reserved.
random generation context-free languages unranking non-redundant generation weighted grammars recursive random generation