{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:50:35Z","timestamp":1744217435481},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_47","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"567-580","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Bertoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimiliano","family":"Goldwurm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Massimo","family":"Santini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"47_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974."},{"key":"47_CR2","volume-title":"The Theory of Parsing, Translation and Compiling-Vol.I: Parsing","author":"A. V. Aho","year":"1972","unstructured":"A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation and Compiling-Vol.I: Parsing. Prentice Hall, Englewood Cliffs, NJ, 1972."},{"key":"47_CR3","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01275489","volume":"3","author":"E. Allender","year":"1993","unstructured":"E. Allender, D. Bruschi, and G. Pighizzini. The complexity of computing maximal word functions. Computational Complexity, 3:368\u2013391, 1993.","journal-title":"Computational Complexity"},{"issue":"4-5-6","key":"47_CR4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1051\/ita\/1998324-601411","volume":"32","author":"A. Avellone","year":"1998","unstructured":"A. Avellone and M. Goldwurm. Analysis of algorithms for the recognition of rational and context-free trace languages. RAIRO Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications, 32(4-5-6):141\u2013152, 1998.","journal-title":"RAIRO Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications"},{"key":"47_CR5","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1142\/9789814261456_0005","volume-title":"The Book of Traces","author":"A. Bertoni","year":"1995","unstructured":"A. Bertoni, M. Goldwurm, G. Mauri, and N. Sabadini. Counting techniques for inclusion, equivalence and membership problems. In V. Diekert and G. Rozenberg, editors, The Book of Traces, chapter 5, pages 131\u2013164. World Scientific, Singapore, 1995."},{"issue":"2","key":"47_CR6","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90023-U","volume":"86","author":"A. Bertoni","year":"1991","unstructured":"A. Bertoni, M. Goldwurm, and N. Sabadini. The complexity of computing the number of strings of given length in context-free languages. Theoretical Computer Science, 86(2):325\u2013342, 1991.","journal-title":"Theoretical Computer Science"},{"key":"47_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/3-540-08138-0_11","volume-title":"Proceedings of the 3rd GI Conference on Theoretical Computer Science","author":"F.-J. Brandenburg","year":"1977","unstructured":"F.-J. Brandenburg. On one-way auxiliary pushdown automata. In H. Waldschmidt H. Tzschach and H. K.-G. Walter, editors, Proceedings of the 3rd GI Conference on Theoretical Computer Science, volume 48 of Lecture Notes in Computer Science, pages 132\u2013144, Darmstadt, FRG, March 1977. Springer."},{"issue":"5","key":"47_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF01185866","volume":"28","author":"C. Choffrut","year":"1995","unstructured":"C. Choffrut and M. Goldwurm. Rational transductions and complexity of counting problems. Mathematical Systems Theory, 28(5):437\u2013450, 1995.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"47_CR9","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18(1):4\u201318, January 1971.","journal-title":"Journal of the ACM"},{"key":"47_CR10","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/978-3-642-59126-6_8","volume-title":"Handbook on Formal Languages","author":"V. Diekert","year":"1997","unstructured":"V. Diekert and Y. M\u00e9tivier. Partial commutation and traces. In G. Rozenberg and A. Salomaa, editors, Handbook on Formal Languages, volume III, pages 457\u2013527. Springer, Berlin-Heidelberg, 1997."},{"key":"47_CR11","doi-asserted-by":"crossref","DOI":"10.1142\/2563","volume-title":"The Book of Traces","author":"V. Diekert","year":"1995","unstructured":"V. Diekert and G. Rozenberg. The Book of Traces. World Scientific, Singapore, 1995."},{"issue":"2","key":"47_CR12","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J. Earley","year":"1970","unstructured":"J. Earley. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94\u2013102, February 1970.","journal-title":"Communications of the ACM"},{"key":"47_CR13","first-page":"225","volume-title":"Trends in Theoretical Computer Science","author":"P. Flajolet","year":"1988","unstructured":"P. Flajolet. Mathematical methods in the analysis of algorithms and data structures. In Egon B\u00f6rger, editor, Trends in Theoretical Computer Science, chapter 6, pages 225\u2013304. Computer Science Press, Rockville, Maryland, 1988."},{"issue":"1\u20132","key":"47_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","volume":"132","author":"P. Flajolet","year":"1994","unstructured":"P. Flajolet, P. Zimmerman, and B. Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1\u20132):1\u201335, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"47_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(95)00025-8","volume":"54","author":"M. Goldwurm","year":"1995","unstructured":"M. Goldwurm. Random generation of words in an algebraic language in linear binary space. Information Processing Letters, 54(4):229\u2013233, 1995.","journal-title":"Information Processing Letters"},{"issue":"1","key":"47_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1006\/inco.1997.2621","volume":"134","author":"V. Gore","year":"1997","unstructured":"V. Gore, M. Jerrum, S. Kannan, Z. Sweedyk, and S. Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Information and Computation, 134(1):59\u201374, 10 April 1997.","journal-title":"Information and Computation"},{"key":"47_CR17","volume-title":"Introduction to Formal Language Theory","author":"M. A. Harrison","year":"1978","unstructured":"M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, Reading, MA, 1978."},{"issue":"4","key":"47_CR18","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1137\/0212044","volume":"12","author":"T. Hickey","year":"1983","unstructured":"T. Hickey and J. Cohen. Uniform random generation of strings in a context-free language. SIAM Journal on Computing, 12(4):645\u2013655, nov 1983.","journal-title":"SIAM Journal on Computing"},{"key":"47_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.2307\/2282952","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13\u201330, 1963.","journal-title":"Journal of the American Statistical Association"},{"key":"47_CR20","volume-title":"Introduction to Automata Theory, Language, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA, 1979."},{"issue":"2\u20133","key":"47_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. R. Jerrum","year":"1986","unstructured":"M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43(2\u20133):169\u2013188, 1986.","journal-title":"Theoretical Computer Science"},{"key":"47_CR22","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"R. M. Karp","year":"1989","unstructured":"R. M. Karp, M. Luby, and N. Madras. Monte-carlo approximation algorithms for enumeration problems. Journal of Algorithms, 10:429\u2013448, 1989.","journal-title":"Journal of Algorithms"},{"key":"47_CR23","unstructured":"D. E. Knuth and A. C. Yao. The complexity of nonuniform random number generation. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 357\u2013428. Academic Press, 1976."},{"key":"47_CR24","unstructured":"C. Lautemann. On pushdown and small tape. In K. Wagener, editor, Dirk-Siefkes, zum 50. Geburststag (proceedings of a meeting honoring Dirk Siefkes on his fiftieth birthday), pages 42\u201347. Technische Universit\u00e4t Berlin and Universit\u00e4t Ausgburg, 1988."},{"issue":"2","key":"47_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(94)90033-7","volume":"49","author":"H. G. Mairson","year":"1994","unstructured":"H. G. Mairson. Generating words in a context-free language uniformly at random. Information Processing Letters, 49(2):95\u201399, January 1994.","journal-title":"Information Processing Letters"},{"key":"47_CR26","unstructured":"M. Santini. Random Uniform Generation and Approximate Counting of Combinatorial Structures. PhD thesis, Dipartimento di Scienze dell\u2019Informazione \u2014 Universit\u00e0 degli Studi di Milano, 1999."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T09:49:58Z","timestamp":1558259398000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_47","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}