{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:55:33Z","timestamp":1775818533785,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540108566","type":"print"},{"value":"9783540387695","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10856-4_72","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:33:01Z","timestamp":1330173181000},"page":"33-45","source":"Crossref","is-referenced-by-count":61,"title":["Probabilistic two-way machines"],"prefix":"10.1007","author":[{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Adleman L.M. On distinguishing prime numbers from composite numbers. \u2014 Proc. 21st Symp. on Foundations of Computer Science, IEEE, 1980, 387\u2013406.","DOI":"10.1109\/SFCS.1980.28"},{"key":"3_CR2","first-page":"245","volume":"15","author":"J.M. Barzdin","year":"1965","unstructured":"Barzdin J.M. Complexity of recognition of palindromes by Turing machines. \u2014 Problemy kibernetiki, v.15, Moscow, Nauka, 1965, 245\u2013248 (Russian).","journal-title":"Problemy kibernetiki"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Chandra A.K. and Stockmeyer L.J. Alternation. \u2014 Proc. 17th Symp. on Foundations of Computer Science, IEEE, 1976, 98\u2013108.","DOI":"10.1109\/SFCS.1976.4"},{"key":"3_CR4","first-page":"201","volume":"233","author":"R. Freivalds","year":"1975","unstructured":"Freivalds R. Fast computation by probabilistic Turing machines. \u2014 U\u010denye Zapiski Latviiiskogo Gosudarstvennogo Universiteta, v.233, 1975, 201\u2013205. (Russian).","journal-title":"U\u010denye Zapiski Latviiiskogo Gosudarstvennogo Universiteta"},{"key":"3_CR5","first-page":"839","volume-title":"Probabilistic machines can use less running time","author":"R. Freivalds","year":"1977","unstructured":"Freivalds R. Probabilistic machines can use less running time. Information Processing '77, IFIP, North-Holland, 1977, 839\u2013842."},{"issue":"1","key":"3_CR6","first-page":"60","volume":"239","author":"R. Freivalds","year":"1978","unstructured":"Freivalds R. Recognition of languages with high probability on different classes of automata. \u2014 Doklady Akad. Nauk SSSR, v.239, No.1, 1978, 60\u201362 (Russian) = Soviet Math. Doklady, v.19, No.2, 1978, 295\u2013298.","journal-title":"Doklady Akad. Nauk SSSR"},{"key":"3_CR7","unstructured":"Freivalds R. Recognition of languages by finite multihead probabilistic and deterministic automata. \u2014 Avtomatika i vy\u010dislitelnaja tekhnika, 1979, No.3, 15\u201320 (Russian)."},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume":"74","author":"R. Freivalds","year":"1979","unstructured":"Freivalds R. Fast probabilistic algorithms. \u2014 Lecture Notes in Computer Science, v.74, 1979, 57\u201369.","journal-title":"Lecture Notes in Computer Science"},{"issue":"4","key":"3_CR9","first-page":"96","volume":"15","author":"R. Freivalds","year":"1979","unstructured":"Freivalds R. Recognition of languages by probabilistic Turing machines in real time and by pushdown automata. \u2014 Problemy pereda\u010di informacii, v.15, No.4, 1979, 96\u2013101 (Russian).","journal-title":"Problemy pereda\u010di informacii"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Gardner M. Mathematical games. \u2014 Scientific American, 1978, No.2, 5\u20139.","DOI":"10.1038\/scientificamerican0878-18"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Gill J.T. Computational complexity of probabilistic Turing machines. \u2014 Proc. 6th ACM Symp. on Theory of Computing, 1974, 91\u201395.","DOI":"10.1145\/800119.803889"},{"key":"3_CR12","first-page":"214","volume-title":"Real-time computations of two-way multihead finite automata","author":"L. Janiga","year":"1979","unstructured":"Janiga L. Real-time computations of two-way multihead finite automata. \u2014 Proc. Fundamentals of Computation Theory FCT'79, Berlin, Akademie, 1979, 214\u2013218."},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Jung H. Relationships between probabilistic and deterministic tape complexity. \u2014 MFCS'81, 1981.","DOI":"10.1007\/3-540-10856-4_101"},{"key":"3_CR14","unstructured":"Kovalenko I.N. A note on complexity of probabilistic and deterministic finite automata. \u2014 Kibernetika, 1965, No.2, 35\u201336 (Russian)."},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Kozen D. On parallelism in Turing machines. \u2014 Proc. 17th Symp. on Foundations of Computer Science, IEEE, 1976, 89\u201397.","DOI":"10.1109\/SFCS.1976.20"},{"key":"3_CR16","unstructured":"Kuklin Yu.I. Two-way probabilistic automata. \u2014 Avtomatika i vy\u010dislitelnaja tekhnika, 1973, No.5, 35\u201336 (Russian)."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Ladner R.E., Lipton R.J., Stockmeyer L.J. Alternating pushdown automata. \u2014 Proc. 19th Symp. on Foundations of Computer Science, IEEE, 1978, 92\u2013106.","DOI":"10.1109\/SFCS.1978.6"},{"key":"3_CR18","first-page":"183","volume":"34","author":"K. Leeuw de","year":"1956","unstructured":"de Leeuw K., Moore E.F., Shannon C.E., Shapiro N. Computability by probabilistic machines. \u2014 Automata Studies, Ann. of Math.Studies, v.34, Princeton Univ.Press, 1956, 183\u2013212.","journal-title":"Automata Studies, Ann. of Math.Studies"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Lewis II P.M., Stearns R.E., Hartmanis J. Memory bounds for recognition of context-free and context-sensitive languages. \u2014 IEEE Conf.Rec.Switch.Circuit Theory and Logic. Design, N.Y., 1965, 191\u2013202.","DOI":"10.1109\/FOCS.1965.14"},{"key":"3_CR20","unstructured":"Monien B., and Sudborough I.H. On elimination of nondeterminism in tape-bounded computations. \u2014 Lecture Notes in Computer Science, v.71, 1979."},{"key":"3_CR21","unstructured":"Rabin M.O. Probabilistic algorithms. \u2014 Algorithms and Complexity. New Directions and Recent Results, Academic Press, 1976, 21\u201340."},{"issue":"3","key":"3_CR22","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin M.O. Probabilistic automata. \u2014 Information and Control, v.6, No.3, 1963, 230\u2013245.","journal-title":"Information and Control"},{"key":"3_CR23","unstructured":"Rabin M.O. Two-way finite automata. \u2014 Proc. Summer Institute of Symbolic Logic, Cornell, 1957, 366\u2013369."},{"issue":"2","key":"3_CR24","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J.C. Shepherdson","year":"1959","unstructured":"Shepherdson J.C. The reduction of two-way automata to one-way automata. \u2014 IBM Journal of Research and Development, v.3, No.2, 1959, 198\u2013200.","journal-title":"IBM Journal of Research and Development"},{"key":"3_CR25","series-title":"Relatorio Interno","volume-title":"On tape-bounded probabilistic computations","author":"J. Simon","year":"1977","unstructured":"Simon J. On tape-bounded probabilistic computations. \u2014 Relatorio Interno No.75, Universidade Enstadul de Campinas, Brazil, 1977."},{"issue":"1","key":"3_CR26","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"Solovay R., Strassen V. Fast Monte-Carlo test for primality. \u2014 SIAM Journal on Computing, v.6, No.1, 1977, 84\u201385.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Stearns R.E., Hartmanis J., Lewis P.M. II. Hierarchies of memory limited computations. \u2014 IEEE Conf.Rec.Switch. Circuit Theory and Logic. Design, N.Y., 1965, 197\u2013190.","DOI":"10.1109\/FOCS.1965.11"},{"key":"3_CR28","volume-title":"Research in Mathematical Logic and Theory of Algorithms","author":"B.A. Trakhtenbrot","year":"1974","unstructured":"Trakhtenbrot B.A. Notes on complexity of computation by probabilistic machines. \u2014 Research in Mathematical Logic and Theory of Algorithms, Moscow, Comp.Ctr. Acad.Sci.USSR, 1974 (Russian) = Algebraische Modelle, Kategorien und Gruppoide. Studien zur Algebra und Ihre Anwendungen, 7, Berlin, Akademie, 1979, 165\u2013178 (German)."},{"key":"3_CR29","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1007\/3-540-10003-2_106","volume":"85","author":"P.M.B. Vit\u00e1nyi","year":"1980","unstructured":"Vit\u00e1nyi P.M.B. On the power of real-time Turing machines under varying specifications. \u2014 Lecture Notes in Computer Science, v.85, 1980, 658\u2013671.","journal-title":"Lecture Notes in Computer Science"},{"key":"3_CR30","first-page":"75","volume":"2","author":"S.V. Yablonskii","year":"1959","unstructured":"Yablonskii S.V. On algorithmic difficulties in the synthesis of minimal switching circuits. \u2014 Problemy kibernetiki, v.2, Moscow, Fizmatgiz, 1959, 75\u2013121 (Russian).","journal-title":"Problemy kibernetiki"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1981"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10856-4_72.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:04:03Z","timestamp":1605625443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10856-4_72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108566","9783540387695"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-10856-4_72","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981]]}}}