{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T17:05:44Z","timestamp":1785603944678,"version":"3.56.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319214993","type":"print"},{"value":"9783319215006","type":"electronic"}],"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-21500-6_20","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"252-263","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Unary Probabilistic and Quantum Automata on Promise Problems"],"prefix":"10.1007","author":[{"given":"Aida","family":"Gainutdinova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abuzer","family":"Yakary\u0131lmaz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-319-09704-6_6","volume-title":"Descriptional Complexity of Formal Systems","author":"F Ablayev","year":"2014","unstructured":"Ablayev, F., Gainutdinova, A., Khadiev, K., Yakary\u0131lmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 53\u201364. Springer, Heidelberg (2014)"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/3-540-44612-5_9","volume-title":"Mathematical Foundations of Computer Science 2000","author":"F Ablayev","year":"2000","unstructured":"Ablayev, F., Gainutdinova, A.: On the lower bounds for one-way quantum automata. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 132\u2013140. Springer, Heidelberg (2000)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/11505877_7","volume-title":"Developments in Language Theory","author":"F Ablayev","year":"2005","unstructured":"Ablayev, F., Gainutdinova, A.: Complexity of quantum uniform and nonuniform automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 78\u201387. Springer, Heidelberg (2005)"},{"issue":"2","key":"20_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ic.2005.04.003","volume":"203","author":"FM Ablayev","year":"2005","unstructured":"Ablayev, F.M., Gainutdinova, A., Karpinski, M., Moore, C., Pollett, C.: On the computational power of probabilistic and quantum branching program. Information Computation 203(2), 145\u2013162 (2005)","journal-title":"Information Computation"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: FOCS 1998, pp. 332\u2013341 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"issue":"7","key":"20_CR6","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.ipl.2012.01.001","volume":"112","author":"A Ambainis","year":"2012","unstructured":"Ambainis, A., Yakary\u0131lmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters 112(7), 289\u2013291 (2012)","journal-title":"Information Processing Letters"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Apostol, T.M.: Introduction to Analytic Number Theory. Springer (1976)","DOI":"10.1007\/978-1-4757-5579-4"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-319-13350-8_12","volume-title":"Computing with New Resources","author":"MP Bianchi","year":"2014","unstructured":"Bianchi, M.P., Mereghetti, C., Palano, B.: Complexity of promise problems on classical and quantum automata. In: Calude, C.S., Freivalds, R., Kazuo, I. (eds.) Gruska Festschrift. LNCS, vol. 8808, pp. 161\u2013175. Springer, Heidelberg (2014)"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Condon, A., Lipton, R.J.: On the complexity of space bounded interactive proofs (extended abstract). In: FOCS 1989, pp. 462\u2013467 (1989)","DOI":"10.1109\/SFCS.1989.63519"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Gainutdinova, A., Yakaryilmaz, A.: Unary probabilistic and quantum automata on promise problems. Technical Report arxiv.org\/abs\/1502.01462, arXiv (2015)","DOI":"10.1007\/978-3-319-21500-6_20"},{"key":"20_CR11","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)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11685654_12","volume-title":"Theoretical Computer Science","author":"O Goldreich","year":"2006","unstructured":"Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254\u2013290. Springer, Heidelberg (2006)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Gruska, J., Qiu, D., Zheng, S.: Generalizations of the distributed Deutsch-Jozsa promise problem. Technical report, arXiv (2014). arXiv:1402.7254","DOI":"10.1017\/S0960129515000158"},{"key":"20_CR14","unstructured":"Gruska, J., Qiu, D., Zheng, S.: Potential of quantum finite automata with exact acceptance. Technical Report arXiv:1404.1689 (2014)"},{"issue":"1","key":"20_CR15","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. International Journal of Natural Computing 1(1), 70\u201385 (2010)","journal-title":"International Journal of Natural Computing"},{"key":"20_CR16","volume-title":"Finite Markov Chains","author":"JG Kemeny","year":"1960","unstructured":"Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, Princeton (1960)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: las vegas and one-way protocols. In: STOC 2000, pp. 644\u2013651 (2000)","DOI":"10.1145\/335305.335396"},{"issue":"5","key":"20_CR18","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1051\/ita:2001106","volume":"35","author":"C Mereghetti","year":"2001","unstructured":"Mereghetti, C., Palano, B., Pighizzini, G.: Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata. Theoretical Informatics and Applications 35(5), 477\u2013490 (2001)","journal-title":"Theoretical Informatics and Applications"},{"issue":"1\u20132","key":"20_CR19","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. Theoretical Computer Science 237(1\u20132), 275\u2013306 (2000)","journal-title":"Theoretical Computer Science"},{"key":"20_CR20","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 Digital Courier 1, 426\u2013435 (2005)","journal-title":"IPSJ Digital Courier"},{"key":"20_CR21","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-Testing. LNCS, vol. 8939, pp. 352\u2013363. Springer, Heidelberg (2015)"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Nakanishi, M., Yakary\u0131lmaz, A.: Classical and quantum counter automata on promise problems (2014). (arXiv:1412.6761) (Accepted to CIAA2015)","DOI":"10.1007\/978-3-319-22360-5_19"},{"key":"20_CR23","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2000)"},{"key":"20_CR24","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)"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Salomaaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Texts and monographs in computer science. Springer-Verlag (1978)","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","first-page":"208","volume-title":"Computing with New Resources","author":"AC Cem Say","year":"2014","unstructured":"Cem Say, A.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":"20_CR27","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Encyclopedia of Complexity and System Science. In: Quantum computational complexity (chapter). Springer (2009). arXiv:0804.3401","DOI":"10.1007\/978-0-387-30440-3_428"},{"issue":"9&10","key":"20_CR28","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., Cem Say, A.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":"6","key":"20_CR29","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., Cem Say, A.C.: Unbounded-error quantum computation with small space bounds. Information and Computation 279(6), 873\u2013892 (2011)","journal-title":"Information and Computation"},{"key":"20_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-319-04921-2_49","volume-title":"Language and Automata Theory and Applications","author":"S Zheng","year":"2014","unstructured":"Zheng, S., Gruska, J., Qiu, D.: On the state complexity of semi-quantum finite automata. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 601\u2013612. Springer, Heidelberg (2014)"},{"key":"20_CR31","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2013.06.005","volume":"499","author":"S Zheng","year":"2013","unstructured":"Zheng, S., Qiu, D., Gruska, J., Li, L., Mateus, P.: State succinctness of two-way finite automata with quantum and classical states. Theoretical Computer Science 499, 98\u2013112 (2013)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T09:29:47Z","timestamp":1748510987000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}