## A quasi-polynomial-time algorithm for sampling words from a
context-free language

**Vivek Gore and Mark Jerrum**
*Abstract:* A quasi-polynomial-time algorithm is presented
for sampling almost uniformly at random from the *n*-slice of
the language *L*(*G*) generated by an arbitrary
context-free grammar *G*. (The *n*-slice of a language
*L* over an alphabet *alph* is the subset of *L* of
words of length exactly *n*.) The time complexity of the
algorithm is *epsilon*^{-2}(*n*
|*G*|)^{O(log n)}, where the parameter
*epsilon* bounds the variation of the output distribution from
uniform, and |*G*| is a natural measure of the size of grammar
*G*. The algorithm applies to a class of language sampling
problems that includes slices of context-free languages as a proper
subclass.

*LFCS report ECS-LFCS-95-326,
July 1995.*

Previous |

Index |

Next