Santini
le 7 Décembre 2000 à 14h30
au LRI, Salle 101
(Université de Milan)
On the sequential and circuit complexity of the random generation
problem for polynomially ambiguous context-free languages
Résumé/Abstract :
We study the sequential and circuit complexity of generating at random,
under uniform distribution, a word of length n from a given
context-free language. We show that for every inherently finitely
ambiguous context-free language the problem can be solved in
O(n2 log n) time on a RAM under
logarithmic cost criterion; moreover we show that for every inherently
polynomially ambiguous context-free language the problem can be solved
by a logspace-uniform family of probabilistic boolean circuits of polynomial
size and O(log2 n) depth. Using a suitable notion
of reducibility (similar to the NC1-reducibility), we also
show the relationship between random generation problems and classical
computational complexity classes such as DIV, L and DET.