{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:24:29Z","timestamp":1725665069572},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:22:11Z","timestamp":1330280531000},"page":"175-185","source":"Crossref","is-referenced-by-count":0,"title":["Weak and strong recognition by 2-way randomized automata"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"A.Ambainis, The complexity of probabilistic versus deterministic finite automata. Lecture Notes in Computer Science, 1178(1996).","DOI":"10.1007\/BFb0009499"},{"issue":"4","key":"15_CR2","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"C. Dwork, L. Stockmeyer, Finite state verifiers I: The power of interaction. Journal of ACM, 39, 4 (1992), 800\u2013828.","journal-title":"Journal of ACM"},{"key":"15_CR3","first-page":"839","volume-title":"Information Processing'77","author":"R. Freivalds","year":"1977","unstructured":"R. Freivalds, Probabilistic machines can use less running time. Information Processing'77, IFIP, North-Holland, 1977, 839\u2013842."},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume":"74","author":"R. Freivalds","year":"1979","unstructured":"R. Freivalds, Fast probabilistic algorithms. Lecture Notes in Computer Science, 74 (1979), 57\u201369.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds, Probabilistic two-way machines. Lecture Notes in Computer Science, 118(1981), 33\u201345.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR6","doi-asserted-by":"crossref","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 finite multitape automata. Information Processing Letters, 13(1981), 195\u2013198.","journal-title":"Information Processing Letters"},{"key":"15_CR7","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/3-540-58201-0_100","volume":"820","author":"R. Freivalds","year":"1994","unstructured":"R. Freivalds, M. Karpinski, Lower space bounds for randomized computation. Lecture Notes in Computer Science, 820 (1994), 580\u2013592.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0022-0000(86)90045-0","volume":"33","author":"A.G. Greenberg","year":"1986","unstructured":"A.G. Greenberg, A. Weiss, A lower bound for probabilistic algorithms for finite state machines. Journal of Computer and System Sciences, 33 (1986), 88\u2013105.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/3-540-54458-5_73","volume":"529","author":"J. Ka\u0146eps","year":"1991","unstructured":"J. Ka\u0146eps, Regularity of one-letter languages acceptable by 2-way finite probabilistic automata. Lecture Notes in Computer Science, 529 (1991), 287\u2013296.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/0890-5401(87)90057-5","volume":"75","author":"M. Karpinski","year":"1987","unstructured":"M. Karpinski, R. Verbeek, On the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes. Information and Computation, 75(1987), 178\u2013189.","journal-title":"Information and Computation"},{"key":"15_CR11","unstructured":"J.G.Kemeny, J.L.Snell, Finite Markov Chains. Van Nostrand, 1960."},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/978-1-4684-9455-6","volume-title":"Denumerable Markov Chains","author":"J.G. Kemeny","year":"1976","unstructured":"J.G. Kemeny, J.L. Snell, and A.W. Knapp, Denumerable Markov Chains. Springer-Verlag, Berlin et al., 1976, 416 pages."},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1007\/3-540-10843-2_40","volume":"115","author":"K.N. King","year":"1981","unstructured":"K.N. King, Alternating multihead finite automata. Lecture Notes in Computer Science, 115 (1981), 506\u2013520.","journal-title":"Lecture Notes in Computer Science"},{"key":"15_CR14","unstructured":"H.R.Lewis, and Ch.H.Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, 1981, 466 pages."},{"key":"15_CR15","unstructured":"M.O.Rabin, Two-way finite automata. Proc.Summer Institute of Symbolic Logic, Cornell, 1957, 366\u2013369."},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J.C. Shepherdson","year":"1959","unstructured":"J.C. Shepherdson, The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(1959), 198\u2013200.","journal-title":"IBM Journal of Research and Development"},{"key":"15_CR17","first-page":"115+1","volume":"843","author":"A. Szepietowski","year":"1994","unstructured":"A. Szepietowski, Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science, 843 (1994), 115+1 pages.","journal-title":"Lecture Notes in Computer Science"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:43:20Z","timestamp":1619559800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}