Page 1

Displaying 1 – 10 of 10

Showing per page

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

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.

Random Generation for Finitely Ambiguous Context-free Languages

Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini (2010)

RAIRO - Theoretical Informatics and Applications

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(n2 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.

Currently displaying 1 – 10 of 10

Page 1