{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T04:09:33Z","timestamp":1748578173329,"version":"3.41.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319223599"},{"type":"electronic","value":"9783319223605"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22360-5_19","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T08:24:42Z","timestamp":1437985482000},"page":"224-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Classical and Quantum Counter Automata on Promise Problems"],"prefix":"10.1007","author":[{"given":"Masaki","family":"Nakanishi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Amano, M., Iwama, K.: Undecidability on quantum finite automata. In: STOC 1999: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 368\u2013375 (1999)","DOI":"10.1145\/301250.301344"},{"issue":"1","key":"19_CR2","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-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287(1), 299\u2013311 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R Cleve","year":"1998","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. A 454, 339\u2013354 (1998)","journal-title":"Proc. R. Soc. A"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400, 97\u2013117 (1985)","journal-title":"Proc. R. Soc. Lond. A"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problem by quantum computation. Proc. R. Soc. A 439, 553\u2013558 (1992)","journal-title":"Proc. R. Soc. A"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/3-540-09526-8_5","volume-title":"Mathematical Foundations of Computer Science 1979","author":"R Freivalds","year":"1979","unstructured":"Freivalds, R.: Fast probabilistic algorithms. In: Be\u010dv\u00e1\u0159, J. (ed.) Mathematical Foundations of Computer Science 1979. LNCS, vol. 74, pp. 57\u201369. Springer, Heidelberg (1979)"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Freivalds, R.: Probabilistic two-way machines. In: Proceedings of the International Symposium on Mathematical Foundations of Computer Science, pp. 33\u201345 (1981)","DOI":"10.1007\/3-540-10856-4_72"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Gainutdinova, A., Yakary\u0131lmaz, A.: Unary probabilistic and quantum automata on promise problems. In: Developments in Language Theory, LNCS, vol. 9168, pp. 252\u2013263. Springer International Publishing (2015). (arXiv:1502.01462)","DOI":"10.1007\/978-3-319-21500-6_20"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/978-3-319-09704-6_12","volume-title":"Descriptional Complexity of Formal Systems","author":"V Geffert","year":"2014","unstructured":"Geffert, V., Yakary\u0131lmaz, A.: Classical automata on promise problems. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 126\u2013137. Springer, Heidelberg (2014). (ECCC:TR14-136)"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","volume":"7","author":"SA Greibach","year":"1978","unstructured":"Greibach, S.A.: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7, 311\u2013324 (1978)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"70","DOI":"10.4018\/jncr.2010010104","volume":"1","author":"M Hirvensalo","year":"2010","unstructured":"Hirvensalo, M.: Quantum automata with open time evolution. Int. J. Nat. Comput. 1(1), 70\u201385 (2010)","journal-title":"Int. J. Nat. Comput."},{"issue":"8","key":"19_CR12","doi-asserted-by":"publisher","first-page":"982","DOI":"10.1016\/j.ic.2009.11.001","volume":"208","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On probabilistic pushdown automata. Inf. Comput. 208(8), 982\u2013995 (2010)","journal-title":"Inf. Comput."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/3-540-47849-3_31","volume-title":"SOFSEM\u201999: Theory and Practice of Informatics","author":"M Kravtsev","year":"1999","unstructured":"Kravtsev, M.: Quantum finite one-counter automata. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol. 1725, p. 431. Springer, Heidelberg (1999)"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2011.10.021","volume":"419","author":"L Li","year":"2012","unstructured":"Li, L., Qiu, D., Zou, X., Li, L., Wu, L., Mateus, P.: Characterizations of one-way general quantum finite automata. Theoret. Comput. Sci. 419, 73\u201391 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"19_CR16","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C Moore","year":"2000","unstructured":"Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoret. Comput. Sci. 237(1\u20132), 275\u2013306 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"426","DOI":"10.2197\/ipsjdc.1.426","volume":"1","author":"Y Murakami","year":"2005","unstructured":"Murakami, Y., Nakanishi, M., Yamashita, S., Watanabe, K.: Quantum versus classical pushdown automata in exact computation. IPSJ Digit. Cour. 1, 426\u2013435 (2005)","journal-title":"IPSJ Digit. Cour."},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-662-46078-8_29","volume-title":"SOFSEM 2015: Theory and Practice of Computer Science-Testing","author":"M Nakanishi","year":"2015","unstructured":"Nakanishi, M.: Quantum pushdown automata with a garbage tape. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 352\u2013363. Springer, Heidelberg (2015). arXiv:1402.3449"},{"key":"19_CR19","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"MO Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Inf. Control 6, 230\u2013243 (1963)","journal-title":"Inf. Control"},{"key":"19_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1007\/978-3-319-08846-4_24","volume-title":"Implementation and Application of Automata","author":"J Rashid","year":"2014","unstructured":"Rashid, J., Yakary\u0131lmaz, A.: Implications of quantum automata for contextuality. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 318\u2013331. Springer, Heidelberg (2014). arXiv:1404.2761"},{"issue":"5","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1142\/S012905411250013X","volume":"23","author":"ACC Say","year":"2012","unstructured":"Say, A.C.C., Yakary\u0131lmaz, A.: Quantum counter automata. Int. J. Found. Comput. Sci. 23(5), 1099\u20131116 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","first-page":"208","volume-title":"Computing with New Resources","author":"ACC Say","year":"2014","unstructured":"Say, A.C.C., Yakary\u0131lmaz, A.: Quantum finite automata: A modern introduction. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 208\u2013222. Springer, Heidelberg (2014)"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3, 198\u2013200 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"19_CR25","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2006","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 2nd edn. Thomson Course Technology, USA (2006)","edition":"2"},{"key":"19_CR26","volume-title":"Encyclopedia of Complexity and System Science","author":"J Watrous","year":"2009","unstructured":"Watrous, J.: Quantum computational complexity. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and System Science. Springer, New york (2009). arXiv:0804.3401"},{"issue":"4","key":"19_CR27","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1051\/ita\/2012018","volume":"46","author":"A Yakary\u0131lmaz","year":"2012","unstructured":"Yakary\u0131lmaz, A.: Superiority of one-way and realtime quantum machines. RAIRO Theoret. Inf. Appl. 46(4), 615\u2013641 (2012)","journal-title":"RAIRO Theoret. Inf. Appl."},{"key":"19_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-38536-0_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Yakary\u0131lmaz","year":"2013","unstructured":"Yakary\u0131lmaz, A.: One-counter verifiers for decidable languages. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 366\u2013377. Springer, Heidelberg (2013)"},{"issue":"1","key":"19_CR29","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. Nat. Comput. 11(1), 81\u201394 (2012)","journal-title":"Nat. Comput."},{"issue":"6","key":"19_CR30","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. Inf. Comput. 279(6), 873\u2013892 (2011)","journal-title":"Inf. Comput."},{"issue":"1\u20133","key":"19_CR31","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. Theoret. Comput. Sci. 334(1\u20133), 275\u2013297 (2005)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22360-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T18:43:58Z","timestamp":1748544238000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22360-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319223599","9783319223605"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22360-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}