Skip to Main content Skip to Navigation
Conference papers

Multi-dimensional Boltzmann Sampling of Languages

Olivier Bodini 1 Yann Ponty 2, 3
1 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : We address the uniform random generation of words from a context-free language (over an alphabet of size $k$), while constraining every letter to a targeted frequency of occurrence. Our approach consists in a multidimensional extension of Boltzmann samplers. We show that, under mostly $\textit{strong-connectivity}$ hypotheses, our samplers return a word of size in $[(1- \epsilon)n, (1+ \epsilon)n]$ and exact frequency in $\mathcal{O}(n^{1+k/2})$ expected time. Moreover, if we accept tolerance intervals of width in $\Omega (\sqrt{n})$ for the number of occurrences of each letters, our samplers perform an approximate-size generation of words in expected $\mathcal{O}(n)$ time. We illustrate our approach on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:34 PM
Last modification on : Wednesday, September 16, 2020 - 5:10:15 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:09:36 AM


Publisher files allowed on an open archive


  • HAL Id : hal-00450763, version 4


Olivier Bodini, Yann Ponty. Multi-dimensional Boltzmann Sampling of Languages. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), Jun 2010, Vienna, Austria. pp.49-64. ⟨hal-00450763v4⟩