Sampling almost uniformly from a context-free language

Vivek Gore

(University of Edinburgh)

We present an algorithm 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 $\Sigma$ is the subset $L \cap \Sigma^n$ of words of length exactly $n$.) The algorithm runs in time $m^{O(\log m)}$, where $m = \max\{n|G|, \log \varepsilon^{-1}\}$, $|G|$ is a natural measure of the size of the grammar $G$, and $\varepsilon$ bounds the variation of the output distribution from uniform. The algorithm uses a couple of old, simple and beautiful results, one from circuit complexity and the other from the area of Monte Carlo approximation algorithms. In this talk I shall try to explain these two results and then show how they are used in our algorithm. This is joint work with Dr Mark Jerrum.
Tuesday 7th November 1995, 14:30
Seminar Room 322
Department of Computer Science