IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishWe 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 |
Copyright © 2021