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), p. 499-512 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2001-01-01
Classification:  68Q45,  68Q25 
@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},
     volume = {35},
     year = {2001},
     pages = {499-512},
     mrnumber = {1922291},
     zbl = {1005.68091},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 499-512. http://gdmltest.u-ga.fr/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 413592 | Zbl 0326.68005

[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 408321

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

[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 483712 | Zbl 0359.68055

[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 152391 | Zbl 0148.00804

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

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

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

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

[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 1290534 | Zbl 0799.68143

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

[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 1448522 | Zbl 0879.68065

[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 642197 | Zbl 0481.68042

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

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

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

[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 855970 | Zbl 0597.68056

[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 431601 | Zbl 0395.65004

[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 1266949 | Zbl 0795.68120

[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 1314820 | Zbl 0998.68062