We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in 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 -NAuxPDA with polynomially bounded ambiguity.
@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, Volume 35 (2001) no. 6, pp. 499-512. http://archive.numdam.org/item/ITA_2001__35_6_499_0/
[1] The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). | MR | Zbl
, and ,[2] The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972). | MR
and ,[3] The complexity of computing maximal word functions. Comput. Complexity 3 (1993) 368-391. | MR | Zbl
, and ,[4] 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] 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
and ,[6] Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math. 10 (1964) 267-270. | Zbl
,[7] Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. | MR | Zbl
,[8] Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 (1999) 233-248. | MR | Zbl
and ,[9] An efficient context-free parsing algorithm. Commun. ACM 13 (1970) 94-102. | Zbl
,[10] A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132 (1994) 1-35. | MR | Zbl
, and ,[11] Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett. 54 (1995) 229-233. | MR | Zbl
,[12] A quasi-polynomial-time algorithm for sampling words from a context-free language. Inform. and Comput. 134 (1997) 59-74. | MR | Zbl
, , , and ,[13] Mathematics for the analysis of algorithms, Vol. 1. Birkhäuser, Basel, CH, Progress in Comput. Sci. (1981). | MR | Zbl
and ,[14] Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). | MR | Zbl
,[15] Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 (1963) 645-655. | MR | Zbl
and ,[16] Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979). | MR | Zbl
and ,[17] Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986) 169-188. | MR | Zbl
, and ,[18] 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
and ,[19] 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] Generating words in a context-free language uniformly at random. Inform. Process. Lett. 49 (1994) 95-99. | MR | Zbl
,[21] Random Uniform Generation and Approximate Counting of Combinatorial Structures, Ph.D. Thesis. Dipartimento di Scienze dell'Informazione (1999).
,[22] Turing Machines with Sublogarithmic Space. Springer Verlag, Lecture Notes in Comput. Sci. 843 (1994). | MR | Zbl
,