{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:25Z","timestamp":1760202505728},"reference-count":27,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1987,11,1]],"date-time":"1987-11-01T00:00:00Z","timestamp":562723200000},"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":9390,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1987,11]]},"DOI":"10.1016\/0890-5401(87)90057-5","type":"journal-article","created":{"date-parts":[[2004,12,1]],"date-time":"2004-12-01T19:24:20Z","timestamp":1101929060000},"page":"178-189","source":"Crossref","is-referenced-by-count":20,"title":["On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes"],"prefix":"10.1016","volume":"75","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Rutger","family":"Verbeek","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(87)90057-5_BIB1","series-title":"Proceedings, 20th IEEE Found. of Comput. Sci.","first-page":"218","article-title":"Random walks, traversal sequences and the complexity of maze problems","author":"Aeliunas","year":"1979"},{"key":"10.1016\/0890-5401(87)90057-5_BIB2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF00264016","article-title":"Lower bounds on space complexity for context-free recognition","volume":"12","author":"Alt","year":"1979","journal-title":"Acta Inform."},{"key":"10.1016\/0890-5401(87)90057-5_BIB3","series-title":"Proceedings, 9th ACM Sympos. on Theory of Comput.","first-page":"151","article-title":"Reducibility, randomness and intractability","author":"Adleman","year":"1977"},{"key":"10.1016\/0890-5401(87)90057-5_BIB4","series-title":"Proceedings, Int. Colloq. Automate Lang. & Programm. '76","first-page":"338","article-title":"Lower bounds for the space complexity of context-free recognition","author":"Alt","year":"1976"},{"key":"10.1016\/0890-5401(87)90057-5_BIB5","series-title":"6th Algebra and Logic Seminar","first-page":"42","article-title":"On one class of Turing machines (Minsky machines)","author":"Bardzin","year":"1962"},{"key":"10.1016\/0890-5401(87)90057-5_BIB6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","article-title":"Parallel computation for well-endowed rings and space-bounded probabilistic machines","volume":"58","author":"Borodin","year":"1983","journal-title":"Inform. and Control"},{"key":"10.1016\/0890-5401(87)90057-5_BIB7","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA \u2260 NPA \u2260 co-NPA with Probability 1","volume":"10","author":"Bennet","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(87)90057-5_BIB8","series-title":"Proceedings, 14th ACM Sympos. on Theory of Comput.","first-page":"310","article-title":"Isomorphism of graphs with bounded eigenvalue multiplicity","author":"Babai","year":"1982"},{"key":"10.1016\/0890-5401(87)90057-5_BIB9","series-title":"Proceedings, 24th IEEE Found. of Comput. Sci.","first-page":"304","article-title":"Lower bounds on graph threading by probabilistic machines","author":"Berman","year":"1983"},{"key":"10.1016\/0890-5401(87)90057-5_BIB10","series-title":"Foundations of Computation Theory","first-page":"78","article-title":"The classification of problems which have fast parallel algorithms","volume":"Vol. 158","author":"Cook","year":"1983"},{"key":"10.1016\/0890-5401(87)90057-5_BIB11","author":"Feller","year":"1957"},{"key":"10.1016\/0890-5401(87)90057-5_BIB12","series-title":"Proceedings, Math. Found. Comput. Sci. '81","first-page":"33","article-title":"Probabilistic two-way machines","volume":"Vol. 118","author":"Freivalds","year":"1981"},{"key":"10.1016\/0890-5401(87)90057-5_BIB13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","article-title":"Projections of languages recognizable by probabilistic and alternating finite multitape automata","volume":"13","author":"Freivalds","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0890-5401(87)90057-5_BIB14","series-title":"Foundations of Computation Theory","first-page":"159","article-title":"Space and reversal complexity of probabilistic one-way Turing machines","volume":"Vol. 158","author":"Freivalds","year":"1983"},{"key":"10.1016\/0890-5401(87)90057-5_BIB15","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."},{"key":"10.1016\/0890-5401(87)90057-5_BIB16","author":"Garey","year":"1979"},{"issue":"No. 8","key":"10.1016\/0890-5401(87)90057-5_BIB17","first-page":"193","article-title":"An approach to a unified theory of automata","volume":"46","author":"Hopcroft","year":"1967","journal-title":"Bell System Tech. J."},{"key":"10.1016\/0890-5401(87)90057-5_BIB18","author":"Hopcroft","year":"1979"},{"key":"10.1016\/0890-5401(87)90057-5_BIB19","series-title":"Proceedings, Int. Colloq. Automata Lang. & Programm. '84","first-page":"281","article-title":"On probabilistic tape complexity and fast circuits for matrix inversion problems","volume":"Vol. 172","author":"Jung","year":"1984"},{"key":"10.1016\/0890-5401(87)90057-5_BIB20","series-title":"Proceedings, 15th ACM Sympos. on Theory of Comput.","first-page":"344","article-title":"Alternation and the power of non-determinism","author":"Kannan","year":"1983"},{"key":"10.1016\/0890-5401(87)90057-5_BIB21","series-title":"Proceedings, 6th IEEE Sympos. on Switching Circuit Theory and Logical Design","first-page":"191","article-title":"Memory bounds for recognition of context-free and context-sensitive languages","author":"Lewis","year":"1965"},{"key":"10.1016\/0890-5401(87)90057-5_BIB22","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","article-title":"Recursive unsolvability of Post's problem of \u201cTag\u201d and other topics in the theory of Turing machines","volume":"74","author":"Minsky","year":"1961","journal-title":"Ann. of Math."},{"key":"10.1016\/0890-5401(87)90057-5_BIB23","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(82)90075-5","article-title":"On eliminating non-determinism from Turing machines which use less than logarithmic work tape space","volume":"21","author":"Monien","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90057-5_BIB24","series-title":"Proceedings, 13th ACM Sympos. on Theory of Comput.","first-page":"158","article-title":"Space-bounded probabilistic Turing machine complexity classes are closed under complement","author":"Simon","year":"1981"},{"key":"10.1016\/0890-5401(87)90057-5_BIB25","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","article-title":"Halting Space-bounded computations","volume":"10","author":"Sipser","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0890-5401(87)90057-5_BIB26","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\/0890-5401(87)90057-5_BIB27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0166-218X(83)90023-9","article-title":"Randomised algorithms","volume":"5","author":"Welsh","year":"1983","journal-title":"Discrete Appl. Math."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900575?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540187900575?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T13:28:46Z","timestamp":1549027726000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540187900575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,11]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1987,11]]}},"alternative-id":["0890540187900575"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(87)90057-5","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1987,11]]}}}