![]() |
Discrete Mathematics & Theoretical Computer Science |
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.
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
|