{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:04:39Z","timestamp":1740287079277,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135224"},{"type":"electronic","value":"9783642135231"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13523-1_14","type":"book-chapter","created":{"date-parts":[[2010,6,23]],"date-time":"2010-06-23T04:34:26Z","timestamp":1277267666000},"page":"115-126","source":"Crossref","is-referenced-by-count":0,"title":["Postselection Finite Quantum Automata"],"prefix":"10.1007","author":[{"given":"Oksana","family":"Scegulnaja-Dubrovska","sequence":"first","affiliation":[]},{"given":"Lelde","family":"L\u0101ce","sequence":"additional","affiliation":[]},{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"14_CR1","first-page":"805","volume":"35","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. SIAM Journal on Computing\u00a035(4), 805\u2013824 (2004) (See also quant-ph\/0307149)","journal-title":"SIAM Journal on Computing"},{"issue":"2063","key":"14_CR2","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1098\/rspa.2005.1546","volume":"461","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S.: Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Proceedings of the Royal Society A\u00a0461(2063), 3473\u20133482 (2005) (See also quant-ph\/0412187)","journal-title":"Proceedings of the Royal Society A"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/3-540-51486-4_104","volume-title":"Mathematical Foundations of Computer Science 1989","author":"F.M. Ablayev","year":"1989","unstructured":"Ablayev, F.M.: On Comparing Probabilistic and Deterministic Automata Complexity of Languages. In: Kreczmar, A., Mirkowska, G. (eds.) MFCS 1989. LNCS, vol.\u00a0379, pp. 599\u2013605. Springer, Heidelberg (1989)"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0016230","volume-title":"Mathematical Foundations of Computer Science 1986","author":"F.M. Ablayev","year":"1986","unstructured":"Ablayev, F.M., Freivalds, R.: Why Sometimes Probabilistic Algorithms Can Be More Effective. In: Gruska, J., Rovan, B., Wiedermann, J. (eds.) MFCS 1986. LNCS, vol.\u00a0233, pp. 1\u201314. Springer, Heidelberg (1986)"},{"issue":"5","key":"14_CR5","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D. Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP cap coNP. Journal of the ACM\u00a052(5), 749\u2013765 (2005)","journal-title":"Journal of the ACM"},{"issue":"1","key":"14_CR6","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., \u0136ikusts, A., Mercer, M., Therien, D.: Algebraic Results on Quantum Automata. Theory of Computing Systems\u00a039(1), 165\u2013188 (2006)","journal-title":"Theory of Computing Systems"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-48686-0_17","volume-title":"Computing and Combinatorics","author":"A. Ambainis","year":"1999","unstructured":"Ambainis, A., Bonner, R., Freivalds, R., \u0136ikusts, A.: Probabilities to accept languages by quantum finite automata. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol.\u00a01627, pp. 174\u2013183. Springer, Heidelberg (1999) (See also quant-ph\/9904066)"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proc. FOCS 1998, pp. 332\u2013341 (1998) (See also quant-ph\/9802062)","DOI":"10.1109\/SFCS.1998.743469"},{"issue":"1-3","key":"14_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(02)00393-6","volume":"295","author":"A. Ambainis","year":"2003","unstructured":"Ambainis, A., \u0136ikusts, A.: Exact results for accepting probabilities of quantum automata. Theoretical Computer Science\u00a0295(1-3), 3\u201325 (2003)","journal-title":"Theoretical Computer Science"},{"key":"14_CR10","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., \u0136ikusts, 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.\u00a02010, pp. 75\u201386. Springer, Heidelberg (2001)"},{"key":"14_CR11","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.: Quantum dense coding and quantum finite automata. Journal of ACM\u00a049, 496\u2013511 (2002); Earlier version: STOC 1999 and quant-ph\/9804043","journal-title":"Journal of ACM"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A. Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P.W., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Physical Reviews\u00a0A52, 3457\u20133467 (1995)","journal-title":"Physical Reviews"},{"key":"14_CR13","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 Journal on Computing\u00a026, 1411\u20131473 (1997)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"14_CR14","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) (See also quant-ph\/9903014)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"14_CR15","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01088986","volume":"13","author":"R.G. Bukharaev","year":"1980","unstructured":"Bukharaev, R.G.: Probabilistic automata. Journal of Mathematical Sciences\u00a013(3), 359\u2013386 (1980)","journal-title":"Journal of Mathematical Sciences"},{"issue":"1","key":"14_CR16","first-page":"60","volume":"239","author":"R. Freivalds","year":"1978","unstructured":"Freivalds, R. (Freivald, R.V.): Recognition of languages with high probability on different classes of automata. Dolady Akademii Nauk SSSR\u00a0239(1), 60\u201362 (1978) (Russian)","journal-title":"Dolady Akademii Nauk SSSR"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","volume":"13","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R.: Projections of Languages Recognizable by Probabilistic and Alternating Finite Multitape Automata. Information Processing Letters\u00a013(4\/5), 195\u2013198 (1981)","journal-title":"Information Processing Letters"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BFb0019368","volume-title":"Baltic Computer Science","author":"R. Freivalds","year":"1991","unstructured":"Freivalds, R.: Complexity of Probabilistic Versus Deterministic Automata. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol.\u00a0502, pp. 565\u2013613. Springer, Heidelberg (1991)"},{"issue":"3","key":"14_CR19","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1142\/S0129054108005826","volume":"19","author":"R. Freivalds","year":"2008","unstructured":"Freivalds, R.: Non-Constructive Methods for Finite Probabilistic Automata. International Journal of Foundations of Computer Science\u00a019(3), 565\u2013580 (2008)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"3","key":"14_CR20","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I. Kerenidis","year":"2004","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences\u00a069(3), 395\u2013420 (2004) (See also quant-ph\/0208062)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: Proc. FOCS 1997, pp. 66\u201375 (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"issue":"2","key":"14_CR22","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/S0097539793253851","volume":"27","author":"I.I. Macarie","year":"1998","unstructured":"Macarie, I.I.: Space-Efficient Deterministic Simulation of Probabilistic Automata. SIAM Journal on Computing\u00a027(2), 448\u2013465 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR23","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) (Also quant-ph\/9707031)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"14_CR24","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Information and Control\u00a06(3), 230\u2013245 (1963)","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Unconventional Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13523-1_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T05:14:14Z","timestamp":1740201254000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13523-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135224","9783642135231"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13523-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}