Displaying similar documents to “Computing a glimpse of randomness.”

Random generation for finitely ambiguous context-free languages

Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O ( n 2 log n ) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1 -NAuxPDA with polynomially bounded ambiguity.