Multi-dimensional Boltzmann Sampling of Languages
Olivier Bodini, Yann Ponty
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 strong-connectivity hypotheses, our samplers return a word of size in [(1-ɛ)n, (1+ɛ)n] and exact frequency in O(n1+k/2) expected time. Moreover, if we accept tolerance intervals of width in Ω(√n) for the number of occurrences of each letters, our samplers perform an approximate-size generation of words in expected O(n) time. We illustrate our approach on the generation of Tetris tessellations with uniform statistics in the different types of tetraminoes.
Full Text: PostScript PDF