{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:50:46Z","timestamp":1725558646365},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540202165"},{"type":"electronic","value":"9783540452089"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45208-9_8","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T04:49:20Z","timestamp":1277700560000},"page":"86-96","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds on the Size of Quantum Automata Accepting Unary Languages"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Bertoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Mereghetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beatrice","family":"Palano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proc. 39th Symposium on Foundations of Computer Science, pp. 332\u2013342 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01342185","volume":"29","author":"P. Benioff","year":"1982","unstructured":"Benioff, P.: Quantum mechanical Hamiltonian models of Turing machines. J. Stat. Phys.\u00a029, 515\u2013546 (1982)","journal-title":"J. Stat. Phys."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1006\/inco.2000.2911","volume":"165","author":"A. Bertoni","year":"2001","unstructured":"Bertoni, A., Carpentieri, M.: Regular languages accepted by quantum automata. Information and Computation\u00a0165, 174\u2013182 (2001)","journal-title":"Information and Computation"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(00)00154-7","volume":"262","author":"A. Bertoni","year":"2001","unstructured":"Bertoni, A., Carpentieri, M.: Analogies and differences between quantum and stochastic automata. Theoretical Computer Science\u00a0262, 69\u201381 (2001)","journal-title":"Theoretical Computer Science"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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, Springer, Heidelberg (2003) (to be published)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Golomb rulers and difference sets for succinct quantum automata. Int. J. Found. Comp. Sci. (2003) (to be published)","DOI":"10.1142\/S0129054103002060"},{"key":"8_CR7","unstructured":"Brodsky, A., Pippenger, N.: Characterizations of 1-way quantum finite automata. Technical Report TR-99-03, Department of Computer Science, University of British Columbia (2000)"},{"key":"8_CR8","unstructured":"Bertoni, A., Torelli, M.: Elementi di matematica combinatoria. ISEDI (1977) (in Italian)"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein, E., Vazirani, U.: Quantum complexity theory. SIAM J. Comput.\u00a026, 1411\u20131473 (1997); A preliminary version appeared in Proc. 25th ACM Symp. On Theory of Computation, pp. 11\u201320 (1993)","journal-title":"SIAM J. Comput."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D. Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. Roy. Soc. London Ser. A\u00a0400, 97\u2013117 (1985)","journal-title":"Proc. Roy. Soc. London Ser. A"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R. Feynman","year":"1982","unstructured":"Feynman, R.: Simulating physics with computers. Int. J. Theoretical Physics\u00a021, 467\u2013488 (1982)","journal-title":"Int. J. Theoretical Physics"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1007\/3-540-45655-4_61","volume-title":"Computing and Combinatorics","author":"M. Golovkins","year":"2002","unstructured":"Golovkins, M., Kravtsev, M.: Probabilistic Reversible Automata and Quantum Automata. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 574\u2013583. Springer, Heidelberg (2002)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proc. 28th ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"8_CR14","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska, J.: Quantum Computing. McGraw-Hill, New York (1999)"},{"key":"8_CR15","first-page":"191","volume":"5","author":"J. Gruska","year":"2000","unstructured":"Gruska, J.: Descriptional complexity issues in quantum computing. J. Automata, Languages and Combinatorics\u00a05, 191\u2013218 (2000)","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"8_CR16","first-page":"3","volume":"9","author":"A.S. Holevo","year":"1973","unstructured":"Holevo, A.S.: Some estimates of the information transmitted by quantum communication channels. Problemy Peredachi Informatsii\u00a09, 3\u201311 (1973); English translation in Problems of Information Transmission 9, 177\u2013183 (1973)","journal-title":"Problemy Peredachi Informatsii"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: 38th Symposium on Foundations of Computer Science, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"8_CR18","volume-title":"Introduction to Linear Algebra","author":"M. Marcus","year":"1965","unstructured":"Marcus, M., Minc, H.: Introduction to Linear Algebra. The Macmillan Company, Basingstoke (1965); Reprinted by Dover (1988)"},{"key":"#cr-split#-8_CR19.1","unstructured":"Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Prindle, Weber & Schmidt (1964);"},{"key":"#cr-split#-8_CR19.2","unstructured":"Reprinted by Dover (1992)"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1051\/ita:2002014","volume":"36","author":"C. Mereghetti","year":"2002","unstructured":"Mereghetti, C., Palano, B.: On the size of one-way quantum finite automata with periodic behaviors. Theoretical Informatics and Applications\u00a036, 277\u2013291 (2002)","journal-title":"Theoretical Informatics and Applications"},{"key":"8_CR21","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 grammars. Theoretical Computer Science\u00a0237, 275\u2013306 (2000); A preliminary version of this work appears as Technical Report in 1997","journal-title":"Theoretical Computer Science"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proc. 40th Symposium on Foundations of Computer Science. pp. 369\u2013376 (1999)","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P. Shor","year":"1997","unstructured":"Shor, P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\u00a026, 1484\u20131509 (1997); A preliminary version appeared in Proc. 35th IEEE Symp. on Foundations of Computer Science, pp. 20\u201322 (1994)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45208-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T04:17:35Z","timestamp":1552623455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45208-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202165","9783540452089"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45208-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}