{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T21:47:33Z","timestamp":1724449653788},"reference-count":18,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1983,6,1]],"date-time":"1983-06-01T00:00:00Z","timestamp":423273600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":11004,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1983,6]]},"DOI":"10.1016\/0304-3975(83)90133-0","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T04:17:21Z","timestamp":1027657041000},"page":"105-117","source":"Crossref","is-referenced-by-count":5,"title":["The time-precision tradeoff problem on on-line probabilistic Turing machines"],"prefix":"10.1016","volume":"24","author":[{"given":"Osamu","family":"Watanabe","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(83)90133-0_BIB1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0304-3975(83)90133-0_BIB2","series-title":"IFIP 77","first-page":"839","article-title":"Probabilistic machines can use less running time","author":"Freivald","year":"1977"},{"key":"10.1016\/0304-3975(83)90133-0_BIB3","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0019-9958(69)90463-X","article-title":"Recognition time of context-free language by on-line Turing machines","volume":"15","author":"Gallaire","year":"1969","journal-title":"Information and Control"},{"issue":"4","key":"10.1016\/0304-3975(83)90133-0_BIB4","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational complexity of probabilistic Turing machines","volume":"6","author":"Gill","year":"1977","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/0304-3975(83)90133-0_BIB5","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(80)90063-8","article-title":"Deterministic simulation of probabilistic Turing machine transducers","volume":"12","author":"Gill","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(83)90133-0_BIB6","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0019-9958(67)80008-1","article-title":"A note on computing time for recognition of languages generated by linear grammars","volume":"10","author":"Kasami","year":"1967","journal-title":"Information and Control"},{"issue":"1","key":"10.1016\/0304-3975(83)90133-0_BIB7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/PGEC.1966.264374","article-title":"On-line Turing machine computations","volume":"15","author":"Hennie","year":"1966","journal-title":"IEEE Trans. Electron. Comput."},{"key":"10.1016\/0304-3975(83)90133-0_BIB8","series-title":"Monte Carlo Methods","author":"Hammersley","year":"1964"},{"key":"10.1016\/0304-3975(83)90133-0_BIB9","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","article-title":"Probabilistic automata","volume":"6","author":"Rabin","year":"1963","journal-title":"Information and Control"},{"key":"10.1016\/0304-3975(83)90133-0_BIB10","series-title":"Algorithms and Complexity: New Directions and Recent Results","first-page":"21","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"issue":"2","key":"10.1016\/0304-3975(83)90133-0_BIB11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1137\/0209024","article-title":"Probabilistic algorithms in finite fields","volume":"9","author":"Rabin","year":"1970","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(83)90133-0_BIB12","first-page":"407","article-title":"N-process synchronization by a 4 log2 N-valued shared variable","author":"Rabin","year":"1980","journal-title":"Proc. 21st FOCS"},{"issue":"4","key":"10.1016\/0304-3975(83)90133-0_BIB13","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(83)90133-0_BIB14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0304-3975(81)90032-3","article-title":"On tape-bounded probabilistic Turing machine acceptors","volume":"16","author":"Simon","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(83)90133-0_BIB15","first-page":"158","article-title":"Space-bounded probabilistic Turing machine complexity classes are closed under complement","author":"Simon","year":"1981","journal-title":"Proc. 13th STOC"},{"issue":"4","key":"10.1016\/0304-3975(83)90133-0_BIB16","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast Monte Carlo test for primality","volume":"6","author":"Solovay","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(83)90133-0_BIB17","series-title":"MS Thesis","article-title":"On reliability and efficiency of probabilistic algorithms","author":"Watanabe","year":"1982"},{"key":"10.1016\/0304-3975(83)90133-0_BIB18","first-page":"118","article-title":"On some advantages of nondeterminate machines over probabilistic ones","volume":"21","author":"Freivald","year":"1977","journal-title":"Izvestiya VUZ. Matematika"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397583901330?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397583901330?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T13:55:19Z","timestamp":1555077319000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397583901330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["0304397583901330"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(83)90133-0","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}