{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:32:47Z","timestamp":1725456767516},"publisher-location":"Berlin\/Heidelberg","reference-count":10,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540529535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029629","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:33:46Z","timestamp":1133415226000},"page":"355-361","source":"Crossref","is-referenced-by-count":17,"title":["Minimal nontrivial space complexity of probabilistic one- way turing machines"],"prefix":"10.1007","author":[{"given":"J\u0101nis","family":"Ka\u0146eps","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","volume-title":"Fundamentals of the Theory of Probabilistic Automata","author":"R.G. Bukharaev","year":"1985","unstructured":"R.G. Bukharaev. Fundamentals of the Theory of Probabilistic Automata. Nauka, Moscow, 1985 (Russian)."},{"key":"38_CR2","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, Springer, 118: 33\u201345, 1981.","journal-title":"Lecture Notes in Computer Science, Springer"},{"key":"38_CR3","first-page":"26","volume":"5","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds. Capabilities of various models of one-way probabilistic automata. Izvestiya VUZ, 5: 26\u201334, 1981 (Russian).","journal-title":"Izvestiya VUZ"},{"key":"38_CR4","first-page":"39","volume":"24","author":"R. Freivalds","year":"1985","unstructured":"R. Freivalds. Space and reversal complexity of probabilistic one-way Turing machines. Annals of Discrete Mathematics, 24: 39\u201350, 1985.","journal-title":"Annals of Discrete Mathematics"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"J.T.Gill. Computational complexity of probabilistic Turing machines. In Proc. 6th ACM Symposium on Theory of Computation, 91\u201396, 1974.","DOI":"10.1145\/800119.803889"},{"key":"38_CR6","volume-title":"Introduction into Theory of Automata","author":"V.B. Kudrjavcev","year":"1985","unstructured":"V.B. Kudrjavcev,S.V. Aleshin,A.S. Podkolzin. Introduction into Theory of Automata. Nauka, Moscow, 1985 (Russian)."},{"issue":"3","key":"38_CR7","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"M.O. Rabin. Probabilistic automata. Information and Control 6(3): 230\u2013245, 1963.","journal-title":"Information and Control"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"R.E.Stearns,J.Hartmanis and P.M.Lewis II. Hierarchies of Memory Limited Computation. In Proc. IEEE Symposium on Switching Circuit Theory and Logical Design, 179\u2013190, 1965.","DOI":"10.1109\/FOCS.1965.11"},{"key":"38_CR9","unstructured":"B.A.Trakhtenbrot and J.M.Barzdin. Finite Automata (Behavior and Synthesis). North-Holland, 1972."},{"key":"38_CR10","first-page":"159","volume-title":"Theory of Algorithms and Mathematical Logics","author":"B.A. Trakhtenbrot","year":"1974","unstructured":"B.A. Trakhtenbrot. Notes on computational complexity by probabilistic machines. In Theory of Algorithms and Mathematical Logics, VC AN SSSR, Moscow, 159\u2013176, 1974 (Russian)."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1990"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0029629.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:59:48Z","timestamp":1607551188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540529535"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/bfb0029629","relation":{},"subject":[]}}