{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T22:40:03Z","timestamp":1747435203345,"version":"3.40.5"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_29","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T14:54:29Z","timestamp":1421247269000},"page":"352-363","source":"Crossref","is-referenced-by-count":4,"title":["Quantum Pushdown Automata with a Garbage Tape"],"prefix":"10.1007","author":[{"given":"Masaki","family":"Nakanishi","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.\u00a08614, pp. 53\u201364. Springer, Heidelberg (2014)"},{"key":"29_CR2","unstructured":"Amarilli, A., Jeanmougin, M.: A proof of the pumping lemma for context-free languages through pushdown automata, coRR, abs\/1207.2819 (2012)"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weakness and generalizations. In: Proceedings of the 29th Symposium on Foundations of Computer Science (FOCS 1998), pp. 332\u2013341 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"issue":"1","key":"29_CR4","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. Theoretical Computer Science\u00a0287(1), 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"29_CR5","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\u00a0112(7), 289\u2013291 (2012)","journal-title":"Information Processing Letters"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Bonner, R., Freivalds, R., Kravtsev, M.: Quantum versus probabilistic one-way finite automata with counter. In: Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM2001), pp. 181\u2013190 (2001)","DOI":"10.1007\/3-540-45627-9_15"},{"issue":"5","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1137\/S0097539799353443","volume":"31","author":"A. Brodsky","year":"2002","unstructured":"Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. SIAM Journal on Computing\u00a031(5), 1456\u20131478 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/3-540-44669-9_36","volume-title":"Fundamentals of Computation Theory","author":"M.P. Ciamarra","year":"2001","unstructured":"Ciamarra, M.P.: Quantum reversibility and a new model of quantum automaton. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.\u00a02138, pp. 376\u2013379. Springer, Heidelberg (2001)"},{"key":"29_CR9","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. Proceedings of the Royal Society A\u00a0454, 339\u2013354 (1998)","journal-title":"Proceedings of the Royal Society A"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch, D.: The Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society A\u00a0400, 97\u2013117 (1985)","journal-title":"Proceedings of the Royal Society A"},{"key":"29_CR11","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. Proceedings of the Royal Society A\u00a0439, 553\u2013558 (1992)","journal-title":"Proceedings of the Royal Society A"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Golovkins, M.: Quantum pushdown automata. In: Proceedings of 27th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2000), pp. 336\u2013346 (2000)","DOI":"10.1007\/3-540-44411-4_22"},{"key":"29_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-3-540-85780-8_2","volume-title":"Developments in Language Theory","author":"M. Hirvensalo","year":"2008","unstructured":"Hirvensalo, M.: Various aspects of finite quantum automata. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol.\u00a05257, pp. 21\u201333. Springer, Heidelberg (2008)"},{"issue":"1","key":"29_CR14","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 Research (IJNCR)\u00a01(1), 70\u201385 (2010)","journal-title":"International Journal of Natural Computing Research (IJNCR)"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th Symposium on Foundations of Computer Science (FOCS 1997), pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"29_CR16","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.\u00a01725, pp. 431\u2013440. Springer, Heidelberg (1999)"},{"issue":"1\u20132","key":"29_CR17","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\u00a0237(1\u20132), 275\u2013306 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"10","key":"29_CR18","first-page":"2471","volume":"46","author":"Y. Murakami","year":"2005","unstructured":"Murakami, Y., Nakanishi, M., Yamashita, S., Watanabe, K.: Quantum versus classical pushdown automata in exact computation. IPSJ Journal\u00a046(10), 2471\u20132480 (2005)","journal-title":"IPSJ Journal"},{"key":"29_CR19","doi-asserted-by":"crossref","unstructured":"Nakanishi, M.: Quantum pushdown automata with a garbage tape, arXiv:1402.3449 (2014)","DOI":"10.1007\/978-3-662-46078-8_29"},{"issue":"3","key":"29_CR20","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1093\/ietisy\/e89-d.3.1120","volume":"E89-D","author":"M. Nakanishi","year":"2006","unstructured":"Nakanishi, M., Hamaguchi, K., Kashiwabara, T.: Expressive power of quantum pushdown automata with classical stack operations under the perfect-soundness condition. IEICE Transactions on Information and Systems\u00a0E89-D(3), 1120\u20131127 (2006)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"3","key":"29_CR21","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01694004","volume":"2","author":"W. Ogden","year":"1968","unstructured":"Ogden, W.: A helpful result for proving inherent ambiguity. Mathematical Systems Theory\u00a02(3), 191\u2013194 (1968)","journal-title":"Mathematical Systems Theory"},{"key":"29_CR22","unstructured":"Paschen, K.: Quantum finite automata using ancilla qubits (2000), technical report, University of Karlsruhe (2000), http: www.digbib.ubka.uni-karlsruhe.de"},{"issue":"5","key":"29_CR23","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"},{"issue":"04","key":"29_CR24","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 - Theoretical Informatics and Applications\u00a046(04), 615\u2013641 (2012)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"issue":"1","key":"29_CR25","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 wirte-ony memory. Natural Computing\u00a011(1), 81\u201394 (2012)","journal-title":"Natural Computing"},{"issue":"20","key":"29_CR26","doi-asserted-by":"publisher","first-page":"1932","DOI":"10.1016\/j.tcs.2009.01.029","volume":"410","author":"A. Yakary\u0131lmaz","year":"2009","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Efficient probability amplification in two-way quantum finite automata. Theoretical Computer Science\u00a0410(20), 1932\u20131941 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"29_CR27","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(4), 19\u201340 (2010)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"issue":"6","key":"29_CR28","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"209","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\u00a0209(6), 873\u2013892 (2011)","journal-title":"Information and Computation"},{"issue":"1-3","key":"29_CR29","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"},{"issue":"2","key":"29_CR30","doi-asserted-by":"publisher","first-page":"963","DOI":"10.1016\/S0304-3975(01)00412-1","volume":"289","author":"T. Yamasaki","year":"2002","unstructured":"Yamasaki, T., Kobayashi, H., Tokunaga, Y., Imai, H.: One-way probabilistic reversible and quantum one-counter automata. Theoretical Computer Science\u00a0289(2), 963\u2013976 (2002)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T22:17:11Z","timestamp":1747433831000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}