Random generation for finitely ambiguous context-free languages

Bertoni, Alberto; Goldwurm, Massimiliano; Santini, Massimo

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.

[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