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.
Previous | Index | Next An error occured whilst processing this directive