We show that, for every unambiguous context-free language L, a uniform random word of length n in L can be generated in O(n log n) time by using O(n) binary space. The algorithm is based on a general technique proposed by Flajolet et al. (1993) for the random generation of combinatorial structures.
Random generation of words in an algebraic language in linear binary space / M. Goldwurm. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 54:4(1995), pp. 229-233. [10.1016/0020-0190(95)00025-8]
Random generation of words in an algebraic language in linear binary space
M. GoldwurmPrimo
1995
Abstract
We show that, for every unambiguous context-free language L, a uniform random word of length n in L can be generated in O(n log n) time by using O(n) binary space. The algorithm is based on a general technique proposed by Flajolet et al. (1993) for the random generation of combinatorial structures.
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.
