Multi-dimensional Boltzmann Sampling of context-free Languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2010

Multi-dimensional Boltzmann Sampling of context-free Languages

Résumé

This paper addresses 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 an extended -- multidimensional -- version of the classic Boltzmann samplers~\cite{Duchon2004}. We show that, under mostly \emph{strong-connectivity} hypotheses, our samplers return a word of size in $[(1-\varepsilon)n, (1+\varepsilon)n]$ and exact frequency in $\mathcal{O}(n^{1+k/2})$ expected time. Moreover, if we accept a tolerance interval of length 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 these techniques on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.
Fichier principal
Vignette du fichier
WeightedBoltzmann-Rational.pdf (350.68 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00450763 , version 1 (30-01-2010)
hal-00450763 , version 2 (01-03-2010)
hal-00450763 , version 3 (01-06-2010)
hal-00450763 , version 4 (20-08-2015)

Identifiants

Citer

Olivier Bodini, Yann Ponty. Multi-dimensional Boltzmann Sampling of context-free Languages. 2010. ⟨hal-00450763v2⟩
1181 Consultations
3217 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More