Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T13:22:06.986Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Generation for FinitelyAmbiguous Context-free Languages

Published online by Cambridge University Press:  15 July 2002

Alberto Bertoni ,
Massimiliano Goldwurm  and
Massimo Santini
Alberto Bertoni
Affiliation:
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39/41, 20135 Milano, Italy; ([email protected])
Massimiliano Goldwurm
Affiliation:
Dipartimento di Scienze dell'Informazione, Università degli Studi di Milano, via Comelico 39/41, 20135 Milano, Italy; ([email protected])
Massimo Santini
Affiliation:
Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy; ([email protected])
Get access

Abstract

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(n2 log n) 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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 6: A tribute to Aldo de Luca , November 2001 , pp. 499 - 512
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972).
Allender, E., Bruschi, D. and Pighizzini, G., The complexity of computing maximal word functions. Comput. Complexity 3 (1993) 368-391. CrossRef
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.
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.
Comtet, L., Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math. 10 (1964) 267-270.
Cook, S.A., Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. CrossRef
Denise, A. and Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 (1999) 233-248. CrossRef
Earley, J., An efficient context-free parsing algorithm. Commun. ACM 13 (1970) 94-102. CrossRef
Flajolet, P., Zimmerman, P. and Van Cutsem, B., A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci. 132 (1994) 1-35. CrossRef
Goldwurm, M., Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett. 54 (1995) 229-233. CrossRef
Gore, V., Jerrum, M., Kannan, S., Sweedyk, Z. and Mahaney, S., A quasi-polynomial-time algorithm for sampling words from a context-free language. Inform. and Comput. 134 (1997) 59-74. CrossRef
D.H. Greene and D.E. Knuth, Mathematics for the analysis of algorithms, Vol. 1. Birkhäuser, Basel, CH, Progress in Comput. Sci. (1981).
M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978).
Hickey, T. and Cohen, J., Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 (1963) 645-655. CrossRef
J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979).
Jerrum, M.R., Valiant, L.G. and Vazirani, V.V., Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43 (1986) 169-188. CrossRef
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.
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.
Mairson, H.G., Generating words in a context-free language uniformly at random. Inform. Process. Lett. 49 (1994) 95-99. CrossRef
M. Santini, Random Uniform Generation and Approximate Counting of Combinatorial Structures, Ph.D. Thesis. Dipartimento di Scienze dell'Informazione (1999).
A. Szepietowski, Turing Machines with Sublogarithmic Space. Springer Verlag, Lecture Notes in Comput. Sci. 843 (1994).