{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:15:16Z","timestamp":1746159316751,"version":"3.40.4"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319049205"},{"type":"electronic","value":"9783319049212"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04921-2_49","type":"book-chapter","created":{"date-parts":[[2014,2,5]],"date-time":"2014-02-05T13:52:25Z","timestamp":1391608345000},"page":"601-612","source":"Crossref","is-referenced-by-count":7,"title":["On the State Complexity of Semi-quantum Finite Automata"],"prefix":"10.1007","author":[{"given":"Shenggen","family":"Zheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daowen","family":"Qiu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"49_CR1","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":"49_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. Theoretical Computer Science\u00a0287, 299\u2013311 (2002)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: One-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th FOCS, pp. 332\u2013341 (1998)","key":"49_CR3","DOI":"10.1109\/SFCS.1998.743469"},{"key":"49_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":"7","key":"49_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., Yakaryilmaz, A.: Superiority of exact quantum automata for promise problems. Information Processing Letters\u00a0112(7), 289\u2013291 (2012)","journal-title":"Information Processing Letters"},{"key":"49_CR6","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.tcs.2006.01.042","volume":"356","author":"A. Bertoni","year":"2006","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Some formal tools for analyzing quantum automata. Theoretical Computer Science\u00a0356, 14\u201325 (2006)","journal-title":"Theoretical Computer Science"},{"key":"49_CR7","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1103\/RevModPhys.82.665","volume":"82","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Cleve, R., Massar, S., de Wolf, R.: Nonlocality and Communication Complexity. Rev. Mod. Phys.\u00a082, 665\u2013698 (2010)","journal-title":"Rev. Mod. Phys."},{"key":"49_CR8","doi-asserted-by":"publisher","first-page":"1011","DOI":"10.1137\/0219069","volume":"19","author":"C. Dwork","year":"1990","unstructured":"Dwork, C., Stockmeyer, L.: A time-complexity gap for two-way probabilistic finite state automata. SIAM J. Comput.\u00a019, 1011\u20131023 (1990)","journal-title":"SIAM J. Comput."},{"key":"49_CR9","first-page":"39","volume":"3","author":"R. Freivalds","year":"1982","unstructured":"Freivalds, R.: On the growth of the number of states in result of determinization of probabilistic finite automata. Automatic Control and Computer Sciences\u00a03, 39\u201342 (1982)","journal-title":"Automatic Control and Computer Sciences"},{"issue":"3","key":"49_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(3), 191\u2013218 (2000)","journal-title":"J. Automata, Languages Combin."},{"key":"49_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":"49_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/3-540-45526-4_11","volume-title":"Automata Implementation","author":"G.A. Kiraz","year":"2001","unstructured":"Kiraz, G.A.: Compressed Storage of Sparse Finite-State Transducers. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol.\u00a02214, pp. 109\u2013121. Springer, Heidelberg (2001)"},{"doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proceedings of the 32th STOC, pp. 644\u2013651 (2000)","key":"49_CR13","DOI":"10.1145\/335305.335396"},{"doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of the 38th FOCS, pp. 66\u201375 (1997)","key":"49_CR14","DOI":"10.1109\/SFCS.1997.646094"},{"key":"49_CR15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0065-2458(08)60342-3","volume":"44","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: Communication Complexity. Advances in Computers\u00a044, 331\u2013360 (1997)","journal-title":"Advances in Computers"},{"key":"49_CR16","first-page":"287","volume":"5","author":"C. Mereghetti","year":"2000","unstructured":"Mereghetti, C., Pighizzini, G.: Two-way automata simulations and unary languages. J. Autom. Lang. Comb.\u00a05, 287\u2013300 (2000)","journal-title":"J. Autom. Lang. Comb."},{"key":"49_CR17","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. RAIRO-Inf. Theor. Appl.\u00a035, 477\u2013490 (2001)","journal-title":"RAIRO-Inf. Theor. Appl."},{"key":"49_CR18","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":"49_CR19","volume-title":"Introduction to Probabilistic Automata","author":"A. Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (1971)"},{"key":"49_CR20","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. Qiu","year":"2008","unstructured":"Qiu, D.: 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)"},{"issue":"2","key":"49_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Research and Development\u00a03(2), 115\u2013125 (1959)","journal-title":"IBM J. Research and Development"},{"key":"49_CR22","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)"},{"doi-asserted-by":"crossref","unstructured":"Salomaa, A.: On the reducibility of events represented in automata. In: Annales Academiae Scientiarum Fennicae, volume Series A of I. Mathematica 353 (1964)","key":"49_CR23","DOI":"10.5186\/aasfm.1964.339"},{"issue":"4","key":"49_CR24","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":"49_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-642-31644-9_19","volume-title":"Languages Alive","author":"S.G. Zheng","year":"2012","unstructured":"Zheng, S.G., Qiu, D.W., Li, L.Z., Gruska, J.: One-way finite automata with quantum and classical states. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol.\u00a07300, pp. 273\u2013290. Springer, Heidelberg (2012)"},{"key":"49_CR26","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2013.06.005","volume":"499","author":"S.G. Zheng","year":"2013","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. Theoretical Computer Science\u00a0499, 98\u2013112 (2013)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Zheng, S.G., Gruska, J., Qiu, D.W.: On the state complexity of semi-quantum finite automata. arXiv:1307.2499 (2013)","key":"49_CR27","DOI":"10.1007\/978-3-319-04921-2_49"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04921-2_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:39:40Z","timestamp":1746128380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04921-2_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319049205","9783319049212"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04921-2_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}