Random generation for finitely ambiguous context-free languages

Alberto Bertoni; Massimiliano Goldwurm; Massimo Santini[1]

  • [1] Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • 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 ( n 2 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 - Informatique Théorique et Applications 35.6 (2001): 499-512. <http://eudml.org/doc/92680>.

@article{Bertoni2001,
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(n^2\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.},
affiliation = {Dipartimento di Scienze Sociali, Cognitive e Quantitative, Università degli Studi di Modena e Reggio Emilia, Via Giglioli Valle, 42100 Reggio Emilia, Italy;},
author = {Bertoni, Alberto, Goldwurm, Massimiliano, Santini, Massimo},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {6},
pages = {499-512},
publisher = {EDP-Sciences},
title = {Random generation for finitely ambiguous context-free languages},
url = {http://eudml.org/doc/92680},
volume = {35},
year = {2001},
}

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
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(n^2\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/92680
ER -

References

top
  1. [1] A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974). Zbl0326.68005MR413592
  2. [2] A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation and Compiling - Vol. I: Parsing. Prentice Hall, Englewood Cliffs, NJ (1972). MR408321
  3. [3] E. Allender, D. Bruschi and G. Pighizzini, The complexity of computing maximal word functions. Comput. Complexity 3 (1993) 368-391. Zbl0802.68061MR1262700
  4. [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. Zbl0359.68055MR483712
  5. [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.00804MR152391
  6. [6] L. Comtet, Calcul pratique des coefficients de Taylor d’une fonction algébrique. Enseign. Math. 10 (1964) 267-270. Zbl0166.41702
  7. [7] S.A. Cook, Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971) 4-18. Zbl0222.02035MR292605
  8. [8] A. Denise and P. Zimmermann, Uniform random generation of decomposable structures using floating-point arithmetic. Theoret. Comput. Sci. 218 (1999) 233-248. Zbl0933.68154MR1702062
  9. [9] J. Earley, An efficient context-free parsing algorithm. Commun. ACM 13 (1970) 94-102. Zbl0185.43401
  10. [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.68143MR1290534
  11. [11] M. Goldwurm, Random generation of words in an algebraic language in linear binary space. Inform. Process. Lett. 54 (1995) 229-233. Zbl0875.68532MR1337828
  12. [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.68065MR1448522
  13. [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.68042MR642197
  14. [14] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley, Reading, MA (1978). Zbl0411.68058MR526397
  15. [15] T. Hickey and J. Cohen, Uniform random generation of strings in a context-free language. SIAM J. Comput. 12 (1963) 645-655. Zbl0524.68046MR721004
  16. [16] J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA (1979). Zbl0426.68001MR645539
  17. [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.68056MR855970
  18. [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.65004MR431601
  19. [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. [20] H.G. Mairson, Generating words in a context-free language uniformly at random. Inform. Process. Lett. 49 (1994) 95-99. Zbl0795.68120MR1266949
  21. [21] M. Santini, Random Uniform Generation and Approximate Counting of Combinatorial Structures, Ph.D. Thesis. Dipartimento di Scienze dell’Informazione (1999). 
  22. [22] A. Szepietowski, Turing Machines with Sublogarithmic Space. Springer Verlag, Lecture Notes in Comput. Sci. 843 (1994). Zbl0998.68062MR1314820

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.