Non-redundant random generation from weighted context-free languages

Yann Ponty (1, 2)

1 AMIB - Algorithms and Models for Integrative Biology
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

We address the non-redundant random generation of k words of length n from a context-free language. Additionally, we want to avoid a prede¯ned set of words. We study the limits of a rejection-based approach, whose time complexity is shown to grow exponentially in k in some cases. We propose an alternative recursive algorithm, whose careful implementation allows for a non-redundant generation of k words of size n in O(kn log n) arithmetic operations after the precomputation of O(n) numbers. The overall complexity is therefore dominated by the generation of k words, and the non-redundancy comes at a negligible cost.

Mots clés: Random generation; context-free grammars; weighted combinatorial objects

Domaines: Algorithme et structure de données [cs.DS]

Yann Ponty. Non-redundant random generation from weighted context-free languages. GASCOM - 7th conference on random generation of combinatorial structures - 2008, 2008, Bibbiena, Italy. 12pp. ⟨hal-00548877⟩