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.
Bertoni, Alberto ; Goldwurm, Massimiliano ; Santini, Massimo 1
@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},
year = {2001},
publisher = {EDP Sciences},
volume = {35},
number = {6},
mrnumber = {1922291},
zbl = {1005.68091},
language = {en},
url = {https://www.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 - https://www.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 https://www.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. https://www.numdam.org/item/ITA_2001__35_6_499_0/
[1] , and, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). | Zbl | MR
[2] and, The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972). | MR
[3] , and, The complexity of computing maximal word functions. Comput. Complexity 3 (1993) 368-391. | Zbl | MR
[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. | Zbl | MR
[5] and, 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. | Zbl | MR
[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. | Zbl | MR
[8] and, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 (1999) 233-248. | Zbl | MR
[9] , An efficient context-free parsing algorithm. Commun. ACM 13 (1970) 94-102. | Zbl
[10] , and, A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132 (1994) 1-35. | Zbl | MR
[11] , Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett. 54 (1995) 229-233. | Zbl | MR
[12] ,,, and, A quasi-polynomial-time algorithm for sampling words from a context-free language. Inform. and Comput. 134 (1997) 59-74. | Zbl | MR
[13] and, Mathematics for the analysis of algorithms, Vol. 1. Birkhäuser, Basel, CH, Progress in Comput. Sci. (1981). | Zbl | MR
[14] , Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). | Zbl | MR
[15] and, Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 (1963) 645-655. | Zbl | MR
[16] and, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979). | Zbl | MR
[17] , and, Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986) 169-188. | Zbl | MR
[18] and, 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. | Zbl | MR
[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. | Zbl | MR
[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). | Zbl | MR
