DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional