29 citations · 67 across the 15 of their papers we have counts for
4 papers · 1 filter
Non-redundant random generation from weighted context-free languages
Yann Ponty
We address the non-redundant random generation of k words of length n from a context-free language. Additionally, we want to avoid a predefined set of words. We study the limits of…
Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models
Danièle Gardy, Yann Ponty
The present work analyzes the redundancy of sets of combinatorial objects produced by a weighted random generation algorithm proposed by Denise et al. This scheme associates weight…
Controlled non uniform random generation of decomposable structures
Alain Denise, Yann Ponty, Michel Termier
Consider a class of decomposable combinatorial structures, using different types of atoms $\Atoms = \{\At_1,\ldots ,\At_{|{\Atoms}|}\}$. We address the random generation of such st…
Multi-dimensional Boltzmann Sampling of Languages
Olivier Bodini, Yann Ponty
This paper addresses the uniform random generation of words from a context-free language (over an alphabet of size ), while constraining every letter to a targeted frequency of…