{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T17:39:37Z","timestamp":1769881177873,"version":"3.49.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319192246","type":"print"},{"value":"9783319192253","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-19225-3_24","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"280-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum State Complexity of Formal Languages"],"prefix":"10.1007","author":[{"given":"Marcos","family":"Villagra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"Yamakami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses, and generalizations. In: Proceedings of FOCS 1998, pp. 332\u2013342 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/3-540-44693-1_7","volume-title":"STACS 2001","author":"A Ambainis","year":"2001","unstructured":"Ambainis, A., ikusts, A., Valdats, M.: On the class of languages recognizable by 1-way quantum finite automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 75\u201386. Springer, Heidelberg (2001)"},{"key":"24_CR3","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 finite automata. J. ACM 49, 496\u2013511 (2002)","journal-title":"J. ACM"},{"key":"24_CR4","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 J. Comput. 31, 1456\u20131478 (2002)","journal-title":"SIAM J. Comput."},{"key":"24_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-60246-1_121","volume-title":"Mathematical Foundations of Computer Science 1995","author":"C Damm","year":"1995","unstructured":"Damm, C., Holzer, M.: Automata that take advice. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 149\u2013158. Springer, Heidelberg (1995)"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1007\/s00454-007-9000-7","volume":"38","author":"I Dumer","year":"2007","unstructured":"Dumer, I.: Covering spheres with spheres. Discret. Comput. Geom. 38, 665\u2013679 (2007)","journal-title":"Discret. Comput. Geom."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"3436","DOI":"10.1016\/j.tcs.2010.05.038","volume":"411","author":"R Freivalds","year":"2010","unstructured":"Freivalds, R.: Amount of nonconstructivity in deterministic finite automata. Theor. Comput. Sci. 411, 3436\u20133443 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"1923","DOI":"10.1016\/j.tcs.2009.01.028","volume":"410","author":"R Freivalds","year":"2009","unstructured":"Freivalds, R., Ozols, M., Man\u010dinska, L.: Improved constructions of mixed state quantum automata. Theor. Comput. Sci. 410, 1923\u20131931 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proceedings of FOCS 1997, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0304-3975(95)00005-4","volume":"156","author":"M Krause","year":"1996","unstructured":"Krause, M.: Geometric arguments yield better bounds for threshold circuits and distributed computing. Theor. Comput. Sci. 156, 99\u2013117 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Found. Trends Theor. Comput. Sci. 3, 263\u2013398 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"24_CR12","doi-asserted-by":"crossref","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 determinsitic, nondeterminsitic, probabilistic and quantum finite automata. RAIRO\u2013Theor. Inf. and Applic. 35, 477\u2013490 (2001)","journal-title":"RAIRO\u2013Theor. Inf. and Applic."},{"key":"24_CR13","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.: Quantum automata and quantum languages. Theor. Comput. Sci. 237, 275\u2013306 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"24_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.ipl.2004.02.005","volume":"90","author":"H Nishimura","year":"2004","unstructured":"Nishimura, H., Yamakami, T.: Polynomial time quantum computation with advice. Inf. Process. Lett. 90, 195\u2013204 (2004)","journal-title":"Inf. Process. Lett."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.jcss.2008.12.001","volume":"75","author":"H Nishimura","year":"2009","unstructured":"Nishimura, H., Yamakami, T.: An application of quantum finite automata to interactive proof systems. J. Comput. Syst. Sci. 75, 255\u2013269 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jcss.1999.1655","volume":"59","author":"J Watrous","year":"1999","unstructured":"Watrous, J.: Space-bounded quantum complexity. J. Comput. Syst. Sci. 59, 281\u2013326 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/s00037-003-0177-8","volume":"12","author":"J Watrous","year":"2003","unstructured":"Watrous, J.: On the complexity of simulating space-bounded quantum computations. Comp. Complex. 12, 48\u201384 (2003)","journal-title":"Comp. Complex."},{"key":"24_CR18","first-page":"19","volume":"12","author":"A Yakaryilmaz","year":"2010","unstructured":"Yakaryilmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Disc. Math. Theor. Comput. Sci. 12, 19\u201340 (2010)","journal-title":"Disc. Math. Theor. Comput. Sci."},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.ic.2014.10.003","volume":"239","author":"T Yamakami","year":"2014","unstructured":"Yamakami, T.: One-way reversible and quantum finite automata with advice. Inf. Comput. 239, 122\u2013148 (2014)","journal-title":"Inf. Comput."},{"key":"24_CR20","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1051\/ita\/2014003","volume":"48","author":"S Zheng","year":"2014","unstructured":"Zheng, S., Gruska, J., Qiu, D.: On the state complexity of semi-quantum finite automata. RAIRO\u2013Theor. Inf. and Applic. 48, 187\u2013207 (2014)","journal-title":"RAIRO\u2013Theor. Inf. and Applic."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T17:05:09Z","timestamp":1748451909000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_24","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":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}