| Issue |
RAIRO-Theor. Inf. Appl.
Volume 35, Number 6, November/December 2001
A tribute to Aldo de Luca
|
|
|---|---|---|
| Page(s) | 499 - 512 | |
| DOI | https://doi.org/10.1051/ita:2001128 | |
| Published online | 15 July 2002 | |
Random Generation for Finitely Ambiguous Context-free Languages
1
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano,
via Comelico 39/41, 20135 Milano, Italy; (bertoni@dsi.unimi.it)
2
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano,
via Comelico 39/41, 20135 Milano, Italy; (goldwurm@dsi.unimi.it)
3
Dipartimento di Scienze Sociali, Cognitive e Quantitative,
Università degli Studi di Modena e Reggio Emilia,
Via Giglioli Valle, 42100 Reggio Emilia, Italy; (msantini@unimo.it)
Received:
24
April
2001
Revised:
7
February
2002
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.
Mathematics Subject Classification: 68Q45 / 68Q25
© EDP Sciences, 2001
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.