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.
Random generation for finitely ambiguous context-free languages / M. SANTINI, A. BERTONI, M. GOLDWURM. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 35:6(2001), pp. 499-512.
Random generation for finitely ambiguous context-free languages
M. SANTINIPrimo
;A. BERTONISecondo
;M. GOLDWURMUltimo
2001
Abstract
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
