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.

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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/item/ITA_2001__35_6_499_0/

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). | MR | Zbl

[2] A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972). | MR

[3] E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Complexity 3 (1993) 368-391. | MR | Zbl

[4] F.-J. Brandenburg, On one-way auxiliary pushdown automata, edited by H. Waldschmidt, H. Tzschach and H.K.-G. Walter, in Proc. of the 3rd GI Conference on Theoretical Computer Science. Springer, Darmstadt, FRG, Lecture Notes in Comput. Sci. 48 (1977) 132-144. | MR | Zbl

[5] N. Chomsky and M.-P. Schützenberger, The algebraic theory of context-free languages, edited by P. Braffort and D. Hirschberg. North-Holland, Amsterdam, The Netherlands, Computer Programming and Formal Systems (1963) 118-161. | MR | Zbl

[6] L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math. 10 (1964) 267-270. | Zbl

[7] S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. | MR | Zbl

[8] A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 (1999) 233-248. | MR | Zbl

[9] J. Earley, An efficient context-free parsing algorithm. Commun. ACM 13 (1970) 94-102. | Zbl

[10] P. Flajolet, P. Zimmerman and B. Van Cutsem, A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132 (1994) 1-35. | MR | Zbl

[11] M. Goldwurm, Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett. 54 (1995) 229-233. | MR | Zbl

[12] V. Gore, M. Jerrum, S. Kannan, Z. Sweedyk and S. Mahaney, A quasi-polynomial-time algorithm for sampling words from a context-free language. Inform. and Comput. 134 (1997) 59-74. | MR | Zbl

[13] D.H. Greene and D.E. Knuth, Mathematics for the analysis of algorithms, Vol. 1. Birkhäuser, Basel, CH, Progress in Comput. Sci. (1981). | MR | Zbl

[14] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). | MR | Zbl

[15] T. Hickey and J. Cohen, Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 (1963) 645-655. | MR | Zbl

[16] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979). | MR | Zbl

[17] M.R. Jerrum, L.G. Valiant and V.V. Vazirani, Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986) 169-188. | MR | Zbl

[18] D.E. Knuth and A.C. Yao, The complexity of nonuniform random number generation, edited by J.F. Traub. Academic Press, Algorithms and Complexity: New Directions and Recent Results (1976) 357-428. | MR | Zbl

[19] C. Lautemann, On pushdown and small tape, edited by K. Wagener, Dirk-Siefkes, zum 50. Geburststag (proceedings of a meeting honoring Dirk Siefkes on his fiftieth birthday). Technische Universität Berlin and Universität Ausgburg (1988) 42-47.

[20] H.G. Mairson, Generating words in a context-free language uniformly at random. Inform. Process. Lett. 49 (1994) 95-99. | MR | Zbl

[21] M. Santini, Random Uniform Generation and Approximate Counting of Combinatorial Structures, Ph.D. Thesis. Dipartimento di Scienze dell'Informazione (1999).

[22] A. Szepietowski, Turing Machines with Sublogarithmic Space. Springer Verlag, Lecture Notes in Comput. Sci. 843 (1994). | MR | Zbl