# Random Generation for Finitely Ambiguous Context-free Languages

Alberto Bertoni; Massimiliano Goldwurm; Massimo Santini

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 6, page 499-512
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBertoni, Alberto, Goldwurm, Massimiliano, and Santini, Massimo. "Random Generation for Finitely Ambiguous Context-free Languages." RAIRO - Theoretical Informatics and Applications 35.6 (2010): 499-512. <http://eudml.org/doc/222066>.

@article{Bertoni2010,

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.
},

author = {Bertoni, Alberto, Goldwurm, Massimiliano, Santini, Massimo},

journal = {RAIRO - Theoretical Informatics and Applications},

language = {eng},

month = {3},

number = {6},

pages = {499-512},

publisher = {EDP Sciences},

title = {Random Generation for Finitely Ambiguous Context-free Languages},

url = {http://eudml.org/doc/222066},

volume = {35},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 6

SP - 499

EP - 512

AB -
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.

LA - eng

UR - http://eudml.org/doc/222066

ER -

## References

top- A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). Zbl0326.68005
- A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972).
- E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Complexity3 (1993) 368-391. Zbl0802.68061
- 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. Zbl0148.00804
- L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math.10 (1964) 267-270. Zbl0166.41702
- S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers. J. ACM18 (1971) 4-18. Zbl0222.02035
- A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci.218 (1999) 233-248. Zbl0933.68154
- J. Earley, An efficient context-free parsing algorithm. Commun. ACM13 (1970) 94-102. Zbl0185.43401
- 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. Zbl0799.68143
- M. Goldwurm, Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett.54 (1995) 229-233. Zbl0875.68532
- 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. Zbl0879.68065
- D.H. Greene and D.E. Knuth, Mathematics for the analysis of algorithms, Vol. 1. Birkhäuser, Basel, CH, Progress in Comput. Sci. (1981). Zbl0481.68042
- M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). Zbl0411.68058
- T. Hickey and J. Cohen, Uniform random generation of strings in a context-free language. SIAM J. Comput.12 (1963) 645-655. Zbl0524.68046
- J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979). Zbl0426.68001
- 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. Zbl0597.68056
- 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. Zbl0395.65004
- 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.
- H.G. Mairson, Generating words in a context-free language uniformly at random. Inform. Process. Lett.49 (1994) 95-99. Zbl0795.68120
- 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). Zbl0998.68062

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.