{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:48:01Z","timestamp":1725486481640},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434535"},{"type":"electronic","value":"9783540460114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_22","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T18:54:16Z","timestamp":1182192856000},"page":"262-271","source":"Crossref","is-referenced-by-count":3,"title":["On the Power of Randomized Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"J. Kaneps, D. Geidmanis, R. Freivalds: Tally languages accepted by Monte Carlo pushdown automata. In: RANDOM\u2019 97, Lexture Notes in Computer Science 1269, pp. 187\u2013195.","DOI":"10.1007\/3-540-63248-4_16"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"A.V. Aho, J.E. Hopcroft, and M. Yannakakis, \u201cOn notions of information transfer in VLSI circuits\u201d, Proc. 15th Annual ACM STOCS, ACM 1983, pp. 133\u2013139.","DOI":"10.1145\/800061.808742"},{"key":"22_CR3","unstructured":"L. Babai, \u201cMonte Carlo algorithms in graph isomorphism techniques\u201d, Research Report no. 79-10, D\u00e9partement de math\u00e9matiques et statistique, Universit\u00e9 de Montr\u00e9al, 1979."},{"key":"22_CR4","unstructured":"Duri\u0161, P., Hromkovi\u010d, J., Inone, K.: A separation of determinism, Las Vegas and nondeterminism for picture recognition. In: Proc. IEEE Conference on Computational Complexity, IEEE 2000, pp. 214\u2013228. Full Version: Electronic Colloqium on Computational Complexity, Report No. 27 (2000)."},{"key":"22_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"Las Vegas versus determinism for one-way communication complexity, finite automata and polynomialtime computations","author":"P. \u010euri\u0161","year":"1997","unstructured":"P. \u010euri\u0161, J. Hromkovi\u010d, J.D.P. Rolim, and G. Schnitger, \u201cLas Vegas versus determinism for one-way communication complexity, finite automata and polynomialtime computations\u201d, Proc. STACS\u201997, Lecture Notes in Computer Science 1200, Springer, 1997, pp. 117\u2013128."},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M. Dietzfelbinger","year":"1994","unstructured":"M. Dietzfelbinger, M. Kutylowski, and R. Reischuk, \u201cExact lower bounds for computing Boolean functions on CREW PRAMs\u201d, J. Computer System Sciences 48, 1994, pp. 231\u2013254.","journal-title":"J. Computer System Sciences"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","volume":"13","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds: Projections of languages recognizable by probabilistic and alternating multitape automata. Information Processing Letters 13 (1981), 195\u2013198.","journal-title":"Information Processing Letters"},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill, \u201cComputational complexity of probabilistic Turing machines\u201d, SIAM J. Computing 6, 1977, pp. 675\u2013695.","journal-title":"SIAM J. Computing"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, Communication Complexity and Parallel Computing, Springer 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, \u201cCommunication Protocols-An Exemplary Study of the Power of Randomness\u201d, Handbook on Randomized Computing, (P. Pardalos, S. Kajasekaran, J. Reif, J. Rolim, Eds.), Kluwer Publisher 2001, to appear.","DOI":"10.1007\/978-1-4615-0013-1_14"},{"key":"22_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/3-540-46541-3_12","volume-title":"Tradeoffs between nondeterminism and complexity for communication protocols and branching programs","author":"J. Hromkovi\u010d","year":"2000","unstructured":"J. Hromkovi\u010d, and M. Sauerhoff, \u201cTradeoffs between nondeterminism and complexity for communication protocols and branching programs\u201d, Proc. STACS 2000, Lecture Notes in Computer Science 1770, Springer 2000, pp. 145\u2013156."},{"key":"22_CR12","unstructured":"J. Hromkovi\u010d, G. Schnitger, \u201cOn the power of LasVegas for one-way communication complexity, OBDD\u2019s and finite automata\u201d. Information and Computation, to appear."},{"key":"22_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/3-540-48523-6_40","volume-title":"On the power of Las Vegas II, Two-way finite automata","author":"J. Hromkovi\u010d","year":"1999","unstructured":"J. Hromkovi\u010d, and G. Schnitger, \u201cOn the power of Las Vegas II, Two-way finite automata\u201d, Proc. ICALP\u201999, Lecture Notes in Computer Science 1644, Springer 1999, pp. 433\u2013443. (extended version: to appear in Theoretical Computer Science)"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, and N. Nisan, Communication Complexity, Cambridge University Press 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"22_CR15","unstructured":"Macarie, I, \u201cOn the structure of log-space probabilistic complexity classes.\u201d Technical Report TR-506, Dept. of Computer Science, University of Rochester 1994."},{"key":"22_CR16","unstructured":"Macarie, I., Ogihara, M., \u201cProperties of probabilistic pushdown automata.\u201d Technical Report TR-554, Dept. of Computer Science, University of Rochester 1994."},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, and E. Schmidt, \u201cLas Vegas is better than determinism in VLSI and distributed computing\u201d, Proc. 14th ACM STOC\u201982, ACM 1982, pp. 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0020-0190(99)00129-5","volume":"72","author":"I.I. Macarie","year":"1999","unstructured":"I.I. Macarie, and J.I. Seiferas, \u201cAmplification of slight probabilistic advantage at absolutely no cost in space\u201d, Information Processing Letters 72, 1999, pp. 113\u2013118.","journal-title":"Information Processing Letters"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Ch. Papadimitrou, and M. Sipser, \u201cCommunication complexity\u201d, Proc. 14th ACM STOC, ACM 1982, pp. 196\u2013200, also in J. Computer System Sciences 28, 1984, pp. 260\u2013269.","DOI":"10.1016\/0022-0000(84)90069-2"},{"key":"22_CR20","unstructured":"M. Sauerhoff, \u201cOn nondeterminism versus randomness for read-once branching programs\u201d, Electronic Colloquium on Computational Complexity, TR 97-030, 1997."},{"key":"22_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/3-540-49116-3_46","volume-title":"On the size of randomized OBDDs and read-once branching programs for k-stable functions","author":"M. Sauerhoff","year":"1999","unstructured":"M. Sauerhoff, \u201cOn the size of randomized OBDDs and read-once branching programs for k-stable functions\u201d, Proc. STACS\u2019 99, Lecture Notes in Computer Science 1563, Springer 1999, pp. 488\u2013499."},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"A.C. Yao, \u201cSome complexity questions related to distributed computing\u201d, Proc. 11th ACM STOC, ACM 1979, pp. 209\u2013213.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T00:23:36Z","timestamp":1556497416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}