Geodesic
Random generation for finitely ambiguous context-free languages
Bertoni, Alberto ; Goldwurm, Massimiliano ; Santini, Massimo1
1 Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 499-512

Voir la notice de l'article provenant de la source Numdam

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(n 2 logn) 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.

Classification : 68Q45, 68Q25

Bertoni, Alberto  ; Goldwurm, Massimiliano  ; Santini, Massimo 1

1 Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy; 
@article{ITA_2001__35_6_499_0,
     author = {Bertoni, Alberto and Goldwurm, Massimiliano and Santini, Massimo},
     title = {Random generation for finitely ambiguous context-free languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {499--512},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {6},
     year = {2001},
     mrnumber = {1922291},
     zbl = {1005.68091},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_6_499_0/}
}
TY  - JOUR
AU  - Bertoni, Alberto
AU  - Goldwurm, Massimiliano
AU  - Santini, Massimo
TI  - Random generation for finitely ambiguous context-free languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 499
EP  - 512
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_6_499_0/
LA  - en
ID  - ITA_2001__35_6_499_0
ER  - 
%0 Journal Article
%A Bertoni, Alberto
%A Goldwurm, Massimiliano
%A Santini, Massimo
%T Random generation for finitely ambiguous context-free languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 499-512
%V 35
%N 6
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_6_499_0/
%G en
%F ITA_2001__35_6_499_0
Bertoni, Alberto; Goldwurm, Massimiliano; Santini, Massimo. Random generation for finitely ambiguous context-free languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 499-512. http://geodesic.mathdoc.fr/item/ITA_2001__35_6_499_0/