{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T12:10:19Z","timestamp":1737288619145,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_7","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:04Z","timestamp":1184601244000},"page":"66-80","source":"Crossref","is-referenced-by-count":3,"title":["Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes"],"prefix":"10.1007","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"J. Kaneps, D. Geidmanis, and R. Freivalds, \u201cTally languages accepted by Monte Carlo pushdown automata\u201d, RANDOM\u2019 97, Lexture Notes in Computer Science 1269, pp. 187\u2013195.","DOI":"10.1007\/3-540-63248-4_16"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"P. \u010euri\u0161, J. Hromkovi\u010d, and K. Inone, \u201cA separation of determinism, Las Vegas and nondeterminism for picture recognition\u201d, Proc. IEEE Conference on Computational Complexity, IEEE 2000, pp. 214\u2013228.","DOI":"10.1109\/CCC.2000.856752"},{"key":"7_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"Proc. STACS\u201997","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 polynomial-time computations\u201d, Proc. STACS\u201997, Lecture Notes in Computer Science 1200, Springer, 1997, pp. 117\u2013128."},{"key":"7_CR4","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":"7_CR5","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, \u201cProjections of languages recognizable by probabilistic and alternating multitape automata\u201d, Information Processing Letters 13 (1981), pp. 195\u2013198.","journal-title":"Information Processing Letters"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, Communication Complexity and Parallel Computing, Springer 1997.","DOI":"10.1007\/978-3-662-03442-2"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, \u201cCommunication Protocols \u2014 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":"7_CR8","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, and G. Schnitger, \u201cOn the power of randomized pushdown automata\u201d, 5th Int. Conf. Developments in Language Theory, 2001, pp. 262\u2013271.","DOI":"10.1007\/3-540-46011-X_22"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J. Hromkovi\u010d","year":"2001","unstructured":"J. Hromkovi\u010d, and G. Schnitger, \u201cOn the power of Las Vegas for one-way communication complexity, OBDD\u2019s and finite automata\u201d, Information and Computation, 169, 2001, pp.284\u2013296.","journal-title":"Information and Computation"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00155-9","volume":"262","author":"J. Hromkovi\u010d","year":"2001","unstructured":"J. Hromkovi\u010d, and G. Schnitger, \u201cOn the power of Las Vegas II, Two-way finite automata\u201d, Theoretical Computer Science, 262, 2001, pp. 1\u201324","journal-title":"Theoretical Computer Science"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immermann","year":"1988","unstructured":"Immermann, N, \u201cNondeterministic space is closed under complementation\u201d, SIAM J. Computing, 17 (1988), pp. 935\u2013938.","journal-title":"SIAM J. Computing"},{"issue":"4","key":"7_CR12","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"B. Kalyanasundaram, and G. Schnitger, \u201cThe Probabilistic Communication Complexity of Set Intersection\u201d, SIAM J. on Discrete Math. 5(4), pp. 545\u2013557, 1992.","journal-title":"SIAM J. on Discrete Math."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, and N. Nisan, Communication Complexity, Cambridge University Press 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"7_CR14","unstructured":"I. Macarie, and M. Ogihara, \u201cProperties of probabilistic pushdown automata\u201d, Technical Report TR-554, Dept. of Computer Science, University of Rochester 1994."},{"key":"7_CR15","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":"7_CR16","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"},{"issue":"2","key":"7_CR17","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"A.A. Razborov, \u201cOn the distributional complexity of disjointness\u201d, Theor. Comp. Sci. 106(2), pp. 385\u2013390, 1992.","journal-title":"Theor. Comp. Sci."},{"key":"7_CR18","unstructured":"M. Sauerhoff, \u201cOn nondeterminism versus randomness for read-once branching programs\u201d, Electronic Colloquium on Computational Complexity, TR 97-030, 1997."},{"key":"7_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/3-540-49116-3_46","volume-title":"Proc. STACS\u2019 99","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":"7_CR20","first-page":"96","volume":"33","author":"R. Szelepcs\u011bnyi","year":"1987","unstructured":"R. Szelepcs\u011bnyi, \u201cThe method of forcing for nondeterministic automata\u201d, Ball. EATCS 33, (1987), pp. 96\u2013100.","journal-title":"Ball. EATCS"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:43:43Z","timestamp":1737287023000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}