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).  
  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.  
  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.  
  6. L. Comtet, Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseign. Math.10 (1964) 267-270.  
  7. S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers. J. ACM18 (1971) 4-18.  
  8. A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci.218 (1999) 233-248.  
  9. J. Earley, An efficient context-free parsing algorithm. Commun. ACM13 (1970) 94-102.  
  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.  
  11. M. Goldwurm, Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett.54 (1995) 229-233.  
  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.  
  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).  
  14. M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978).  
  15. T. Hickey and J. Cohen, Uniform random generation of strings in a context-free language. SIAM J. Comput.12 (1963) 645-655.  
  16. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979).  
  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.  
  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.  
  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.  
  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).  

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.