{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:15:13Z","timestamp":1774588513642,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642385353","type":"print"},{"value":"9783642385360","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_32","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"366-377","source":"Crossref","is-referenced-by-count":7,"title":["One-Counter Verifiers for Decidable Languages"],"prefix":"10.1007","author":[{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"32_CR1","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0304-3975(02)00138-X","volume":"287","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A., Watrous, J.: Two\u2013way finite automata with quantum and classical states. Theoretical Computer Science\u00a0287(1), 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"key":"32_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/BFb0030304","volume-title":"Mathematical Foundations of Computer Science 1984","author":"M. Chrobak","year":"1984","unstructured":"Chrobak, M.: Nondeterminism is essential for two-way counter machines. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 240\u2013244. Springer, Heidelberg (1984)"},{"key":"32_CR3","unstructured":"Condon, A.: Complexity Theory: Current Research, chap. The complexity of space bounded interactive proof systems, pp. 147\u2013190. Cambridge University Press (1993)"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: FOCS 1989: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 462\u2013467 (1989)","DOI":"10.1109\/SFCS.1989.63519"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"\u010euri\u0161, P., Galil, Z.: Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (preliminary version). In: STOC 1981: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 177\u2013188 (1981)","DOI":"10.1145\/800076.802471"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0304-3975(82)90087-1","volume":"21","author":"P. \u010euri\u0161","year":"1982","unstructured":"\u010euri\u0161, P., Galil, Z.: Fooling a two way automaton or one pushdown store is better than one counter for two way machines. Theoretical Computer Science\u00a021, 39\u201353 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"32_CR7","doi-asserted-by":"publisher","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"Dwork, C., Stockmeyer, L.: Finite state verifiers I: The power of interaction. Journal of the ACM\u00a039(4), 800\u2013828 (1992)","journal-title":"Journal of the ACM"},{"key":"32_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U., Shamir, A.: Multi-oracle interactive protocols with space bounded verifiers. In: Structure in Complexity Theory Conference, pp. 158\u2013164 (1989)","DOI":"10.1109\/SCT.1989.41822"},{"issue":"1","key":"32_CR9","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2004.09.015","volume":"330","author":"J. Hromkovic","year":"2005","unstructured":"Hromkovic, J., Schnitger, G.: On the power of randomized multicounter machines. Theoretical Computer Science\u00a0330(1), 135\u2013144 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"32_CR10","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.tcs.2005.04.003","volume":"341","author":"A. Inoue","year":"2005","unstructured":"Inoue, A., Ito, A., Inoue, K., Okazaki, T.: Some properties of one-pebble Turing machines with sublogarithmic space. Theoretical Computer Science\u00a0341(1-3), 138\u2013149 (2005)","journal-title":"Theoretical Computer Science"},{"key":"32_CR11","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Machine models and simulations. In: Handbook of Theoretical Computer Science, vol.\u00a0A, pp. 1\u201366 (1990)","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"issue":"3","key":"32_CR12","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M. Minsky","year":"1961","unstructured":"Minsky, M.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u201d and other topics in theory of Turing machines. Annals of Mathematics\u00a074(3), 437\u2013455 (1961)","journal-title":"Annals of Mathematics"},{"key":"32_CR13","unstructured":"Minsky, M.: Computation: Finite and Infinite Machines. Prentice-Hall (1967)"},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1145\/193820.193835","volume":"25","author":"H. Petersen","year":"1994","unstructured":"Petersen, H.: Two-way one-counter automata accepting bounded languages. SIGACT News\u00a025(3), 102\u2013105 (1994)","journal-title":"SIGACT News"},{"key":"32_CR15","unstructured":"Petersen, H.: Private communication (June 2012)"},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-56287-7_121","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"B. Ravikumar","year":"1992","unstructured":"Ravikumar, B.: Some observations on 2-way probabilistic finite automata. In: Shyamasundar, R.K. (ed.) FSTTCS 1992. LNCS, vol.\u00a0652, pp. 392\u2013403. Springer, Heidelberg (1992)"},{"issue":"1-2","key":"32_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.tcs.2007.01.017","volume":"376","author":"B. Ravikumar","year":"2007","unstructured":"Ravikumar, B.: On some variations of two-way probabilistic finite automata models. Theoretical Computer Science\u00a0376(1-2), 127\u2013136 (2007)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"32_CR18","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S012905411250013X","volume":"23","author":"A.C.C. Say","year":"2012","unstructured":"Say, A.C.C., Yakary\u0131lmaz, A.: Quantum counter automata. International Journal of Foundations of Computer Science\u00a023(5), 1099\u20131116 (2012)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Yakary\u0131lmaz, A.: One-counter verifiers for decidable languages. Tech. Rep. ECCC: TR12-091 (2012)","DOI":"10.1007\/978-3-642-38536-0_32"},{"key":"32_CR20","unstructured":"Yakary\u0131lmaz, A.: Public-qubits versus private-coins. Tech. Rep. ECCC: TR12-130 (2012)"},{"issue":"1","key":"32_CR21","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11047-011-9270-0","volume":"11","author":"A. Yakary\u0131lmaz","year":"2012","unstructured":"Yakary\u0131lmaz, A., Freivalds, R., Say, A.C.C., Agadzanyan, R.: Quantum computation with write-only memory. Natural Computing\u00a011(1), 81\u201394 (2012)","journal-title":"Natural Computing"},{"issue":"9&10","key":"32_CR22","doi-asserted-by":"crossref","first-page":"747","DOI":"10.26421\/QIC10.9-10-3","volume":"10","author":"A. Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Information and Computation 10(9&10), 747\u2013770 (2010)","journal-title":"Quantum Information and Computation"},{"issue":"2","key":"32_CR23","first-page":"19","volume":"12","author":"A. Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science\u00a012(2), 19\u201340 (2010)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"issue":"6","key":"32_CR24","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"279","author":"A. Yakary\u0131lmaz","year":"2011","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Unbounded-error quantum computation with small space bounds. Information and Computation\u00a0279(6), 873\u2013892 (2011)","journal-title":"Information and Computation"},{"issue":"1-3","key":"32_CR25","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.tcs.2004.07.034","volume":"334","author":"T. Yamasaki","year":"2005","unstructured":"Yamasaki, T., Kobayashi, H., Imai, H.: Quantum versus deterministic counter automata. Theoretical Computer Science\u00a0334(1-3), 275\u2013297 (2005)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T18:46:56Z","timestamp":1645642016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}