{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:55:36Z","timestamp":1775818536032,"version":"3.50.1"},"reference-count":23,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1016\/j.ic.2021.104744","type":"journal-article","created":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T12:35:17Z","timestamp":1616589317000},"page":"104744","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":4,"special_numbering":"C","title":["Constant-space, constant-randomness verifiers with arbitrarily small error"],"prefix":"10.1016","volume":"288","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0002-5022-178X","authenticated-orcid":false,"given":"M. Utkan","family":"Gezer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.C. Cem","family":"Say","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2021.104744_br0010","series-title":"Language and Automata Theory and Applications","first-page":"184","article-title":"Windable heads and recognizing NL with constant randomness","author":"Gezer","year":"2020"},{"issue":"3","key":"10.1016\/j.ic.2021.104744_br0020","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1006\/jcss.1995.1040","article-title":"Interactive proof systems with polynomially bounded strategies","volume":"50","author":"Condon","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.ic.2021.104744_br0030","series-title":"30th Annual Symposium on Foundations of Computer Science","first-page":"462","article-title":"On the complexity of space bounded interactive proofs","author":"Condon","year":"1989"},{"issue":"4","key":"10.1016\/j.ic.2021.104744_br0040","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","article-title":"Finite state verifiers I: the power of interaction","volume":"39","author":"Dwork","year":"1992","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/j.ic.2021.104744_br0050","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.jcss.2008.12.001","article-title":"An application of quantum finite automata to interactive proof systems","volume":"75","author":"Nishimura","year":"2009","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.ic.2021.104744_br0060","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.11.030","article-title":"Interactive proofs with quantum finite automata","volume":"568","author":"Nishimura","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.ic.2021.104744_br0070","series-title":"Workshop on Quantum and Classical Complexity","first-page":"45","article-title":"Public qubits versus private coins","author":"Yakary\u0131lmaz","year":"2013"},{"key":"10.1016\/j.ic.2021.104744_br0080","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.ic.2015.02.003","article-title":"Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata","volume":"241","author":"Zheng","year":"2015","journal-title":"Inf. Comput."},{"issue":"2","key":"10.1016\/j.ic.2021.104744_br0090","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0022-0000(92)90021-A","article-title":"Multi-oracle interactive protocols with constant space verifiers","volume":"44","author":"Feige","year":"1992","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.ic.2021.104744_br0100","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/s00224-014-9547-7","article-title":"The complexity of debate checking","volume":"57","author":"Demirci","year":"2015","journal-title":"Theory Comput. Syst."},{"issue":"02","key":"10.1016\/j.ic.2021.104744_br0110","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1142\/S0129054116400104","article-title":"Debates with small transparent quantum verifiers","volume":"27","author":"Yakary\u0131lmaz","year":"2016","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"10.1016\/j.ic.2021.104744_br0120","article-title":"Finite state verifiers with constant randomness","volume":"10","author":"Say","year":"2014","journal-title":"Log. Methods Comput. Sci."},{"key":"10.1016\/j.ic.2021.104744_br0130","series-title":"Introduction to the Theory of Computation, Cengage Learning","author":"Sipser","year":"2012"},{"issue":"1\u20132","key":"10.1016\/j.ic.2021.104744_br0140","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.tcs.2010.08.024","article-title":"Complexity of multi-head finite automata: origins and directions","volume":"412","author":"Holzer","year":"2011","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.ic.2021.104744_br0150","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF00289513","article-title":"On non-determinancy in simple computing devices","volume":"1","author":"Hartmanis","year":"1972","journal-title":"Acta Inform."},{"issue":"1","key":"10.1016\/j.ic.2021.104744_br0160","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1051\/ita\/1980140100671","article-title":"Two-way multihead automata over a one-letter alphabet","volume":"14","author":"Monien","year":"1980","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"10.1016\/j.ic.2021.104744_br0170","series-title":"Proceedings of 19th Annual IEEE Symposium on Foundations of Computer Science","first-page":"92","article-title":"Alternating pushdown automata","author":"Ladner","year":"1978"},{"key":"10.1016\/j.ic.2021.104744_br0180","series-title":"International Symposium on Mathematical Foundations of Computer Science","first-page":"291","article-title":"Transforming two-way alternating finite automata to one-way nondeterministic automata","author":"Geffert","year":"2014"},{"issue":"3","key":"10.1016\/j.ic.2021.104744_br0190","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","article-title":"Descriptional and computational complexity of finite automata\u2014a survey","volume":"209","author":"Holzer","year":"2011","journal-title":"Inf. Comput."},{"issue":"3","key":"10.1016\/j.ic.2021.104744_br0200","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1007\/BF01271372","article-title":"The complexity of the max word problem and the power of one-way interactive proof systems","volume":"3","author":"Condon","year":"1993","journal-title":"Comput. Complex."},{"key":"10.1016\/j.ic.2021.104744_br0210","series-title":"Time and memory capacity bounds for machines which recognize squares or palindromes","author":"Cobham","year":"1966"},{"key":"10.1016\/j.ic.2021.104744_br0220","series-title":"Current Trends in Theoretical Computer Science","first-page":"265","article-title":"Time-space lower bounds for NP-complete problems","author":"van Melkebeek","year":"2004"},{"issue":"1","key":"10.1016\/j.ic.2021.104744_br0230","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01744430","article-title":"A time-space tradeoff for language recognition","volume":"17","author":"D\u00fari\u015b","year":"1984","journal-title":"Math. Syst. Theory"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0890540121000596?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0890540121000596?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:16:32Z","timestamp":1760188592000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540121000596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":23,"alternative-id":["S0890540121000596"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ic.2021.104744","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Constant-space, constant-randomness verifiers with arbitrarily small error","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ic.2021.104744","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2021 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}],"article-number":"104744"}}