Olivier Bodini ; Yann Ponty - Multi-dimensional Boltzmann Sampling of Languages

dmtcs:2793 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2793
Multi-dimensional Boltzmann Sampling of Languages

Authors: Olivier Bodini ORCID-iD1; Yann Ponty ORCID-iD2,3

  • 1 Algorithmes, Programmes et Résolution
  • 2 Algorithms and Models for Integrative Biology
  • 3 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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.


Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Random generation,Boltzmann sampling,Context-free languages,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 1804.00841
Source : ScholeXplorer IsRelatedTo DOI 10.1186/s12859-019-2784-7
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1804.00841
Source : ScholeXplorer IsRelatedTo HANDLE 11353/10.1076930
Source : ScholeXplorer IsRelatedTo PMC PMC6482512
Source : ScholeXplorer IsRelatedTo PMID 31023239
  • 1804.00841
  • PMC6482512
  • 31023239
  • 31023239
  • PMC6482512
  • 10.48550/arxiv.1804.00841
  • 11353/10.1076930
  • 10.1186/s12859-019-2784-7
  • 10.1186/s12859-019-2784-7
Fixed-parameter tractable sampling for RNA design with multiple target structures.

7 Documents citing this article

Consultation statistics

This page has been seen 240 times.
This article's PDF has been downloaded 156 times.