We study the circuit complexity of generating at random a word of length n from a given language under uniform distribution. We prove that, for every language accepted in polynomial time by 1-NAuxPDA of polynomially bounded ambiguity, the problem is solvable 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 for regular and context-free languages and classical computational complexity classes such as DIV, L and DET.
On the circuit complexity of random generation problems for regular and context-free languages / M. Goldwurm, B.S. Palano, M. Santini - In: STACS 2001 / [a cura di] A. Ferreira, H. Reichel. - Berlin : Springer, 2001. - ISBN 9783540416951. - pp. 305-316 (( Intervento presentato al 18. convegno Annual Symposium on Theoretical Aspects of Computer Science (STACS) tenutosi a Dresden nel 2001.
Titolo: | On the circuit complexity of random generation problems for regular and context-free languages |
Autori: | GOLDWURM, MASSIMILIANO (Primo) PALANO, BEATRICE SANTA (Secondo) SANTINI, MASSIMO (Ultimo) |
Parole Chiave: | Ambiguous context-free languages; Auxiliary pushdown automata; Circuit complexity; Uniform random generation |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Data di pubblicazione: | 2001 |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/3-540-44693-1_27 |
Tipologia: | Book Part (author) |
Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |