Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Multi-dimensional Bo ...
Conference paper

Multi-dimensional Boltzmann Sampling of Languages

Olivier Bodini ORCID (1), Yann Ponty ORCID (2) (3)
(1) Algorithmes, Programmes et Résolution
(2) Algorithms and Models for Integrative Biology
(3) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2793
License
https://about.hal.science/hal-authorisation-v1
Indicators
844
Views
691
Downloads

Multi-dimensional Boltzmann Sampling of Languages

Olivier Bodini ORCID (1), Yann Ponty ORCID (2) (3)
(1) Algorithmes, Programmes et Résolution
(2) Algorithms and Models for Integrative Biology
(3) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Keywords
  • [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]
  • Boltzmann sampling
  • Context-free languages
  • Random generation
Cited by

Source: OpenCitations

  • Fixed-parameter tractable sampling for RNA design with multiple target structures

    BMC Bioinformatics

    Authors : Stefan Hammer ORCID, Wei Wang ORCID, Sebastian Will ORCID, Yann Ponty ORCID

    Journal reference : Volume 20, 2019, pp. 209

    DOI : 10.1186/s12859-019-2784-7

  • The weighted words collector

    Discrete Mathematics & Theoretical Computer Science

    Authors : Jérémie Du Boisberranger, Danièle Gardy ORCID, Yann Ponty ORCID

    Journal reference : Volume DMTCS Proceedings vol. AQ,..., 2012, pp.

    DOI : 10.46298/dmtcs.2998

  • Boltzmann samplers for first-order differential specifications

    Discrete Applied Mathematics

    Authors : Olivier Bodini ORCID, Olivier Roussel ORCID, Michèle Soria

    Journal reference : Volume 160, 2012, pp. 2563-2572

    DOI : 10.1016/j.dam.2012.05.022

  • Random generation of source vectors with a fixed preponderant property

    Theoretical Computer Science

    Authors : Julien David ORCID

    Journal reference : Volume 1059, 2025, pp. 115630

    DOI : 10.1016/j.tcs.2025.115630

  • Asymptotic Analysis and Random Sampling of Digitally Convex Polyominoes

    Lecture notes in computer science

    Authors : O. Bodini ORCID, Ph. Duchon, A. Jacquot, L. Mutafchiev

    Journal reference : Volume , 2013, pp. 95-106

    DOI : 10.1007/978-3-642-37067-0_9

  • Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications

    arXiv (Cornell University)

    Authors : Olivier Bodini ORCID, Julien David, Philippe Marchal

    Journal reference : Volume , 2016, pp. 97-114

    DOI : 10.1007/978-3-319-29221-2_9

  • Developing Complex RNA Design Applications in the Infrared Framework

    Authors : Hua-Ting Yao ORCID, Yann Ponty ORCID, Sebastian Will ORCID

    Journal reference : Volume 2726, 2012, pp. 285-313

    DOI : 10.1007/978-1-0716-3519-3_12

  • On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height

    Annals of Combinatorics

    Authors : Olivier Bodini ORCID, Danièle Gardy ORCID, Bernhard Gittenberger ORCID, Zbigniew Gołębiewski

    Journal reference : Volume 22, 2018, pp. 45-91

    DOI : 10.1007/s00026-018-0371-7

  • Non-redundant random generation algorithms for weighted context-free grammars

    Theoretical Computer Science

    Authors : William Andrew Lorenz, Yann Ponty ORCID

    Journal reference : Volume 502, 2013, pp. 177-194

    DOI : 10.1016/j.tcs.2013.01.006

  • Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers

    Combinatorics Probability Computing

    Authors : Maciej Bendkowski, Olivier Bodini ORCID, Sergey Dovgal

    Journal reference : Volume 31, 2021, pp. 765-811

    DOI : 10.1017/s0963548321000547

  • RNA inverse folding can be solved in linear time for structures without isolated stacks or base pairs

    Algorithms for Molecular Biology

    Authors : Théo Boury ORCID, Samuel Gardelle ORCID, Laurent Bulteau ORCID, Yann Ponty ORCID

    Journal reference : Volume 20, 2025, pp. 20

    DOI : 10.1186/s13015-025-00278-6

  • Formulae and Asymptotics for Coefficients of Algebraic Functions

    Combinatorics Probability Computing

    Authors : CYRIL BANDERIER ORCID, MICHAEL DRMOTA

    Journal reference : Volume 24, 2014, pp. 1-53

    DOI : 10.1017/s0963548314000728

  • An Unbiased Adaptive Sampling Algorithm for the Exploration of RNA Mutational Landscapes under Evolutionary Pressure

    Authors : Jérôme Waldispühl ORCID, Yann Ponty ORCID

    Journal reference : Volume , 2011, pp. 501-515

    DOI : 10.1007/978-3-642-20036-6_45

  • Distribution of Variables in Lambda-Terms with Restrictions on De Bruijn Indices and De Bruijn Levels

    The Electronic Journal of Combinatorics

    Authors : Bernhard Gittenberger ORCID, Isabella Larcher

    Journal reference : Volume 26, 2019, pp.

    DOI : 10.37236/8579

  • Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models

    Journal of Mathematical Biology

    Authors : Cedric Chauve ORCID, Yann Ponty ORCID, Michael Wallner ORCID

    Journal reference : Volume 80, 2020, pp. 1353-1388

    DOI : 10.1007/s00285-019-01465-x

  • Automatic Exploration of the Natural Variability of RNA Non-Canonical Geometric Patterns with a Parameterized Sampling Technique

    Authors : Boury, Ponty, Reinharz

    Journal reference : Volume , 2023, pp.

    DOI : 10.4230/lipics.wabi.2023.20

  • Infrared: a declarative tree decomposition-powered framework for bioinformatics

    Algorithms for Molecular Biology

    Authors : Hua-Ting Yao ORCID, Bertrand Marchand ORCID, Sarah J. Berkemer ORCID, Yann Ponty ORCID, Sebastian Will ORCID

    Journal reference : Volume 19, 2024, pp. 13

    DOI : 10.1186/s13015-024-00258-2
Preview
Loading PDF preview...