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

Abstract

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

How to cite

top

Bertoni, 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
  1. A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).  Zbl0326.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).  
  3. E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Complexity3 (1993) 368-391.  Zbl0802.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.  
  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.  Zbl0148.00804
  6. L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math.10 (1964) 267-270.  Zbl0166.41702
  7. S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers. J. ACM18 (1971) 4-18.  Zbl0222.02035
  8. A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci.218 (1999) 233-248.  Zbl0933.68154
  9. J. Earley, An efficient context-free parsing algorithm. Commun. ACM13 (1970) 94-102.  Zbl0185.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.  Zbl0799.68143
  11. M. Goldwurm, Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett.54 (1995) 229-233.  Zbl0875.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.  Zbl0879.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).  Zbl0481.68042
  14. M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978).  Zbl0411.68058
  15. T. Hickey and J. Cohen, Uniform random generation of strings in a context-free language. SIAM J. Comput.12 (1963) 645-655.  Zbl0524.68046
  16. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979).  Zbl0426.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.  Zbl0597.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.  Zbl0395.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.  Zbl0795.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).  Zbl0998.68062

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.