{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T09:39:08Z","timestamp":1781257148443,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316432","type":"print"},{"value":"9783642316449","type":"electronic"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31644-9_19","type":"book-chapter","created":{"date-parts":[[2012,7,19]],"date-time":"2012-07-19T02:17:08Z","timestamp":1342664228000},"page":"273-290","source":"Crossref","is-referenced-by-count":16,"title":["One-Way Finite Automata with Quantum and Classical States"],"prefix":"10.1007","author":[{"given":"Shenggen","family":"Zheng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lvzhou","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00224-005-1263-x","volume":"39","author":"A. Ambainis","year":"2006","unstructured":"Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M., Th\u00e9nrien, D.: Algebraic results on quantum automata. Theory Comput. Syst.\u00a039, 165\u2013188 (2006)","journal-title":"Theory Comput. Syst."},{"key":"19_CR2","first-page":"332","volume-title":"Proceedings of the 39th Annual Symposium on Foundations of Computer Science","author":"A. Ambainis","year":"1998","unstructured":"Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 332\u2013341. IEEE Computer Society, Palo Alfo (1998)"},{"key":"19_CR3","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, 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1016\/j.tcs.2009.01.027","volume":"410","author":"A. Ambainis","year":"2009","unstructured":"Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theoretical Computer Science\u00a0410, 1916\u20131922 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A., Nayak, A., Ta-Shma, A., Vazirani, U.: Dense quantum coding and quantum automata. Journal of the ACM\u00a049(4), 496\u2013511 (2002)","journal-title":"Journal of the ACM"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45007-6_1","volume-title":"Developments in Language Theory","author":"A. Bertoni","year":"2003","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Quantum Computing: 1-Way Quantum Automata. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol.\u00a02710, pp. 1\u201320. Springer, Heidelberg (2003)"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.03.032","volume":"340","author":"A. Bertoni","year":"2005","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Small size quantum automata recognizing some regular languages. Theoretical Computer Science\u00a0340, 394\u2013407 (2005)","journal-title":"Theoretical Computer Science"},{"key":"19_CR8","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, 1456\u20131478 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR9","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska, J.: Quantum Computing. McGraw-Hill, London (1999)"},{"key":"19_CR10","first-page":"191","volume":"5","author":"J. Gruska","year":"2000","unstructured":"Gruska, J.: Descriptional complexity issues in quantum computing. J. Automata, Languages Combin.\u00a05, 191\u2013218 (2000)","journal-title":"J. Automata, Languages Combin."},{"key":"19_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addision-Wesley, New York (1979)"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Exponential separation of quantum and classical online space complexity. In: Proceedings of SPAA 2006, pp. 67\u201373 (2006)","DOI":"10.1145\/1148109.1148119"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2008.03.021","volume":"403","author":"L.Z. Li","year":"2008","unstructured":"Li, L.Z., Qiu, D.W.: Determining the equivalence for one-way quantum finite automata. Theoretical Computer Science\u00a0403, 42\u201351 (2008)","journal-title":"Theoretical Computer Science"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"2529","DOI":"10.1016\/j.tcs.2008.08.026","volume":"410","author":"L.Z. Li","year":"2009","unstructured":"Li, L.Z., Qiu, D.W.: A note on quantum sequential machines. Theoretical Computer Science\u00a0410, 2529\u20132535 (2009)","journal-title":"Theoretical Computer Science"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2011.10.021","volume":"419","author":"L.Z. Li","year":"2012","unstructured":"Li, L.Z., Qiu, D.W., Zou, X.F., Li, L.J., Wu, L.H., Mateus, P.: Characterizations of one-way general quantum finite automata. Theoretical Computer Science\u00a0419, 73\u201391 (2012)","journal-title":"Theoretical Computer Science"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1051\/ita:2006007","volume":"40","author":"C. Mereghetti","year":"2006","unstructured":"Mereghetti, C., Palano, B.: Quantum finite automata with control language. RAIRO- Inf. Theor. Appl.\u00a040, 315\u2013332 (2006)","journal-title":"RAIRO- Inf. Theor. Appl."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1051\/ita:2001106","volume":"5","author":"C. Mereghetti","year":"2001","unstructured":"Mereghetti, C., Palano, B., Pighizzini, G.: Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata. RAIRO-Inf. Theor. Appl.\u00a05, 477\u2013490 (2001)","journal-title":"RAIRO-Inf. Theor. Appl."},{"key":"19_CR19","unstructured":"Monras, A., Beige, A., Wiesner, K.: Hidden Quantum Markov Models and non-adaptive read-out of many-body states. ArXiv:1002.2337 (2010)"},{"key":"19_CR20","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, 275\u2013306 (2000)","journal-title":"Theoretical Computer Science"},{"key":"19_CR21","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"19_CR22","unstructured":"Paschen, K.: Quantum finite automata using ancilla qubits. Technical Report, University of Karlsruhe (2000)"},{"key":"19_CR23","volume-title":"Introduction to Probabilistic Automata","author":"A. Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)"},{"key":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-87442-3_1","volume-title":"Advanced Intelligent Computing Theories and Applications. With Aspects of Theoretical and Methodological Issues","author":"D.W. Qiu","year":"2008","unstructured":"Qiu, D.W.: Some Observations on Two-Way Finite Automata with Quantum and Classical States. In: Huang, D.-S., Wunsch II, D.C., Levine, D.S., Jo, K.-H. (eds.) ICIC 2008. LNCS, vol.\u00a05226, pp. 1\u20138. Springer, Heidelberg (2008)"},{"key":"19_CR25","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1201\/b13055-7","volume-title":"Handbook of Finite State Based Models and Applications","author":"D.W. Qiu","year":"2012","unstructured":"Qiu, D.W., Li, L.Z., Mateus, P., Gruska, J.: Quantum Finite Automata. In: Wang, J. (ed.) Handbook of Finite State Based Models and Applications, pp. 113\u2013144. CRC Press, Boca Raton (2012)"},{"key":"19_CR26","unstructured":"Qiu, D.W., Mateus, P., Sernadas, A.: One-way quantum finite automata together with classical states. arXiv:0909.1428"},{"key":"19_CR27","doi-asserted-by":"publisher","first-page":"3006","DOI":"10.1016\/j.tcs.2009.03.040","volume":"410","author":"D.W. Qiu","year":"2009","unstructured":"Qiu, D.W., Yu, S.: Hierarchy and equivalence of multi-letter quantum finite automata. Theoretical Computer Science\u00a0410, 3006\u20133017 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"19_CR28","first-page":"19","volume":"12","author":"A. Yakaryilmaz","year":"2010","unstructured":"Yakaryilmaz, A., Cem Say, A.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"},{"key":"19_CR29","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/j.ic.2011.01.008","volume":"209","author":"A. Yakaryilmaz","year":"2011","unstructured":"Yakaryilmaz, A., Cem Say, A.C.: Unbounded-error quantum computation with small space bounds. Information and Computation\u00a0209, 873\u2013892 (2011)","journal-title":"Information and Computation"},{"issue":"9-10","key":"19_CR30","doi-asserted-by":"crossref","first-page":"747","DOI":"10.26421\/QIC10.9-10-3","volume":"10","author":"A. Yakaryilmaz","year":"2010","unstructured":"Yakaryilmaz, A., Cem Say, A.C.: Languages recognized by nondeterministic quantum finite automata. Quantum Information and Computation\u00a010(9-10), 747\u2013770 (2010)","journal-title":"Quantum Information and Computation"},{"key":"19_CR31","first-page":"41","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1998","unstructured":"Yu, S.: Regular Languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41\u2013110. Springer, Heidelberg (1998)"},{"key":"19_CR32","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1007\/s10773-010-0582-0","volume":"50","author":"S.G. Zheng","year":"2011","unstructured":"Zheng, S.G., Li, L.Z., Qiu, D.W.: Two-Tape Finite Automata with Quantum and Classical States. International Journal of Theoretical Physics\u00a050, 1262\u20131281 (2011)","journal-title":"International Journal of Theoretical Physics"},{"key":"19_CR33","unstructured":"Zheng, S.G., Qiu, D.W., Li, L.Z.: Some languages recongnied by two-way finite automata with quantum and classical states. International Journal of Foundation of Computer Science. Also arXiv:1112.2844 (2011) (to appear)"},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Zheng, S.G., Qiu, D.W., Gruska, J., Li, L.Z., Mateus, P.: State succinctness of two-way finite automata with quantum and classical states. ArXiv:1202.2651 (2012)","DOI":"10.1142\/9789814401531_0052"}],"container-title":["Lecture Notes in Computer Science","Languages Alive"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31644-9_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T21:20:11Z","timestamp":1743801611000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31644-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316432","9783642316449"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31644-9_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}