{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:44:58Z","timestamp":1725486298884},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540416951"},{"type":"electronic","value":"9783540446934"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44693-1_27","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T05:10:18Z","timestamp":1181625018000},"page":"305-316","source":"Crossref","is-referenced-by-count":3,"title":["On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Massimiliano","family":"Goldwurm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beatrice","family":"Palano","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":[[2001,3,16]]},"reference":[{"key":"27_CR1","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":"CSomputational Complexity"},{"issue":"3","key":"27_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0020-0190(90)90089-G","volume":"34","author":"A. Bertoni","year":"1990","unstructured":"A. Bertoni, M. Goldwurm, and P. Massazza. Counting problems and algebraic formal power series in noncommuting variables. Information Processing Letters, 34(3):117\u2013121, April 1990.","journal-title":"Information Processing Letters"},{"issue":"2","key":"27_CR3","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":"27_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/3-540-46541-3_47","volume-title":"Proceedings of 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"A. Bertoni","year":"2000","unstructured":"A. Bertoni, M. Goldwurm, and M. Santini. Random generation and approximate counting of ambiguously described combinatorial structures. In Horst Reichel and Sophie Tison, editors, Proceedings of 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), number 1770 in Lecture Notes in Computer Science, pages 567\u2013580. Springer, 2000."},{"key":"27_CR5","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":"1","key":"27_CR6","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":"27_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"issue":"3","key":"27_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S. A. Cook","year":"1987","unstructured":"S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms, 8(3):385\u2013394, September 1987.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"27_CR9","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(95)00200-6","volume":"159","author":"A. Denise","year":"1996","unstructured":"A. Denise. G\u00e9n\u00e9ration al\u00e9atoire et uniforme de mots de langages rationnels. Theoretical Computer Science, 159(1):43\u201363, 1996.","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"27_CR10","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-2):1\u201335, 1994.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"27_CR11","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"},{"issue":"4","key":"27_CR12","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, November 1983.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"M. Jerrum","year":"1989","unstructured":"M. Jerrum and A. Sinclair. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82:93\u2013133, 1989.","journal-title":"Information and Computation"},{"issue":"2-3","key":"27_CR14","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-3):169\u2013188, 1986.","journal-title":"Theoretical Computer Science"},{"key":"27_CR15","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":"27_CR16","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Computer Science. MIT Press\/Elsevier, 1992."},{"key":"27_CR17","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":"4","key":"27_CR18","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/0217044","volume":"17","author":"G. L. Miller","year":"1988","unstructured":"G. L. Miller, V. Ramachandran, and E. Kaltofen. Efficient parallel evaluation of straightline code and arithmetic circuits. SIAM Journal on Computing, 17(4):687\u2013695, August 1988.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR19","unstructured":"D. B. Searls. The computational linguistics of biological sequences. In Larry Hunter, editor, Artificial Intelligence and Molecular Biology, chapter 2, pages 47\u2013120. AAAI Press, 1992."},{"key":"27_CR20","first-page":"459","volume":"4","author":"R. Smith","year":"1988","unstructured":"R. Smith. A finite state machine algorithm for finding restriction sites and other pattern matching applications. Comput. Appl. Biosci., 4:459\u2013465, 1988.","journal-title":"Comput. Appl. Biosci"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Christopher Balc\u00e1zar, Jos\u00e9; Borodin, Alan; Gasarch, Bill; Immerman, Neil; Papadimitriou, Christos; Ruzzo, Walter; Vit\u00e1nyi, Paul; Wilson, editor, Proceedings of the 6th Annual Conference on Structure in Complexity Theory (SCTC\u2019 91), pages 270\u2013284, Chicago, IL, USA, June 1991. IEEE Computer Society Press.","DOI":"10.1109\/SCT.1991.160269"},{"key":"27_CR22","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener. The Complexity of Boolean Functions. B. G. Teubner, Stuttgart, 1987."}],"container-title":["Lecture Notes in Computer Science","STACS 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44693-1_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T09:12:22Z","timestamp":1550394742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44693-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540416951","9783540446934"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44693-1_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}