{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T12:38:16Z","timestamp":1773405496935,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00236-011-0139-6","type":"journal-article","created":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T08:20:38Z","timestamp":1312186838000},"page":"271-290","source":"Crossref","is-referenced-by-count":15,"title":["Multi-letter quantum finite automata: decidability of the equivalence and minimization of states"],"prefix":"10.1007","volume":"48","author":[{"given":"Daowen","family":"Qiu","sequence":"first","affiliation":[]},{"given":"Lvzhou","family":"Li","sequence":"additional","affiliation":[]},{"given":"Xiangfu","family":"Zou","sequence":"additional","affiliation":[]},{"given":"Paulo","family":"Mateus","sequence":"additional","affiliation":[]},{"given":"Jozef","family":"Gruska","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,8,2]]},"reference":[{"key":"139_CR1","doi-asserted-by":"crossref","unstructured":"Amano, M., Iwama, K.: Undecidability on quantum finite automata. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 368\u2013375. Atlanta, Georgia, USA (1999)","DOI":"10.1145\/301250.301344"},{"key":"139_CR2","doi-asserted-by":"crossref","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 Press, Palo Alfo, California, USA. Also quant-ph\/9802062 (1998)","DOI":"10.1109\/SFCS.1998.743469"},{"key":"139_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2006","unstructured":"Basu S., Pollack R., Roy M.-F.: Algorithms in Real Algebraic Geometry, 2nd Edn. Springer, New York (2006)","edition":"2"},{"key":"139_CR4","doi-asserted-by":"crossref","unstructured":"Belovs, A., Rosmanis, A., Smotrovs, J.: Multi-letter reversible and quantum finite automata. In: Proceedings of the 13th International Conference on Developments in Language Theory (DLT\u20192007). Lecture Notes in Computer Science, vol. 4588, pp. 60\u201371. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-73208-2_9"},{"key":"139_CR5","doi-asserted-by":"crossref","unstructured":"Bertoni, A., Mereghetti, C., Palano, B.: Quantum computing: 1-way quantum automata. In: Proceedings of the 9th International Conference on Developments in Language Theory (DLT\u20192003). Lecture Notes in Computer Science, vol. 2710, pp. 1\u201320. Springer, Berlin (2003)","DOI":"10.1007\/3-540-45007-6_1"},{"key":"139_CR6","doi-asserted-by":"crossref","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":"139_CR7","doi-asserted-by":"crossref","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC \u201988: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. ACM, pp. 460\u2013469. New York, USA (1988)","DOI":"10.1145\/62212.62257"},{"key":"139_CR8","volume-title":"Automata, Languages, and Machines, vol. A","author":"S. Eilenberg","year":"1974","unstructured":"Eilenberg S.: Automata, Languages, and Machines, vol. A. Academic Press, New York (1974)"},{"key":"139_CR9","volume-title":"Computational Methods of Linear Algebra","author":"D.K. Faddeev","year":"1963","unstructured":"Faddeev D.K., Faddeeva V.N.: Computational Methods of Linear Algebra. Freeman, San Francisco (1963)"},{"key":"139_CR10","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212\u2013219. Philadelphia, Pennsylvania, USA (1996)","DOI":"10.1145\/237814.237866"},{"key":"139_CR11","volume-title":"Quantum Computing","author":"J. Gruska","year":"1999","unstructured":"Gruska J.: Quantum Computing. McGraw-Hill, London (1999)"},{"key":"139_CR12","doi-asserted-by":"crossref","unstructured":"Hirvensalo, M.: Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages. In: SOFSEM\u20192007. Lecture Notes in Computer Science, vol. 4362, pp. 309\u2013319. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-69507-3_25"},{"key":"139_CR13","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/BF00290734","volume":"19","author":"J. Hromkovi\u010d","year":"1983","unstructured":"Hromkovi\u010d J.: One-way multihead deterministic finite automata. Acta Inf. 19, 377\u2013384 (1983)","journal-title":"Acta Inf."},{"key":"139_CR14","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":"139_CR15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/BF00288748","volume":"4","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra O.H., Kim C.E.: On 3-head versus 2-head finite automata. Acta Inf. 4, 193\u2013200 (1975)","journal-title":"Acta Inf."},{"key":"139_CR16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s00224-006-1314-y","volume":"40","author":"E. Jeandel","year":"2007","unstructured":"Jeandel E.: Topological automata. Theory Comput. Syst. 40, 397\u2013407 (2007)","journal-title":"Theory Comput. Syst."},{"key":"139_CR17","doi-asserted-by":"crossref","unstructured":"Kondacs, A., Watrous, J.: On the power of finite state automata. In: Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science, pp. 66\u201375. Miami Beach, Florida, USA (1997)","DOI":"10.1109\/SFCS.1997.646094"},{"key":"139_CR18","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.tcs.2006.03.001","volume":"358","author":"L.Z. Li","year":"2006","unstructured":"Li L.Z., Qiu D.W.: Determination of equivalence between quantum sequential machines. Theor. Comput. Sci. 358, 65\u201374 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"139_CR19","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 403, 42\u201351 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"139_CR20","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 410, 2529\u20132535 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"139_CR21","unstructured":"Mateus, P., Qiu, D.W., Li, L.Z.: On the complexity of minimizing probabilistic and quantum automata. Submitted for publication"},{"key":"139_CR22","doi-asserted-by":"crossref","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. Theor. Comput. Sci 237, 275\u2013306 (2000)","journal-title":"Theor. Comput. Sci"},{"key":"139_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":"139_CR24","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1023\/A:1015731405826","volume":"41","author":"D.W. Qiu","year":"2002","unstructured":"Qiu D.W.: Characterization of sequential quantum machines. Int. J. Theor. Phys. 41, 811\u2013822 (2002)","journal-title":"Int. J. Theor. Phys."},{"issue":"2","key":"139_CR25","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s11704-008-0022-y","volume":"2","author":"D.W. Qiu","year":"2008","unstructured":"Qiu D.W., Li L.Z.: An overview of quantum computation models: quantum automata. Frontiers Comput. Sci. China 2(2), 193\u2013207 (2008)","journal-title":"Frontiers Comput. Sci. China"},{"key":"139_CR26","unstructured":"Qiu, D.W., Yu, S.: Hierarchy and equivalence of multi-letter quantum finite automata. Theor. Comput. Sci. 410, 3006\u20133017. Also arXiv: 0812.0852, 2008 (2009)"},{"issue":"3","key":"139_CR27","doi-asserted-by":"crossref","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. Inf. Control 6(3), 230\u2013245 (1963)","journal-title":"Inf. Control"},{"key":"139_CR28","doi-asserted-by":"crossref","unstructured":"Renegar, J.: A faster PSPACE algorithm for deciding the existential theory of the reals. In: Proceedings of 29th IEEE Annual Symposium on Foundations of Computer Science, pp. 291\u2013295. (1988)","DOI":"10.1109\/SFCS.1988.21945"},{"key":"139_CR29","volume-title":"Lattices and Ordered Sets","author":"S. Roman","year":"2008","unstructured":"Roman S.: Lattices and Ordered Sets. Springer, New York (2008)"},{"key":"139_CR30","volume-title":"Handbook of Formal Languages, vol. 1","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds): Handbook of Formal Languages, vol. 1. Springer, Berlin (1997)"},{"issue":"5","key":"139_CR31","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"139_CR32","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A. Tarski","year":"1951","unstructured":"Tarski A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley, CA (1951)"},{"issue":"2","key":"139_CR33","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0221017","volume":"21","author":"W.G. Tzeng","year":"1992","unstructured":"Tzeng W.G.: A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21(2), 216\u2013227 (1992)","journal-title":"SIAM J. Comput."},{"key":"139_CR34","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, Berlin (1998)"},{"key":"139_CR35","doi-asserted-by":"crossref","unstructured":"Yakaryilmaz, A., Cem Say, A.C.: Languages recognized with unbounded error by quantum finite automata. In: Proceedings of the 4th Computer Science Symposium in Russia. Lecture Notes in Comput. Sci. vol. 5675, pp. 356\u2013367. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-03351-3_33"},{"key":"139_CR36","doi-asserted-by":"crossref","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. Inf. Comput. 209, 873\u2013892 (2011)","journal-title":"Inf. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-011-0139-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-011-0139-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-011-0139-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,7]],"date-time":"2025-03-07T23:57:01Z","timestamp":1741391821000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-011-0139-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":36,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["139"],"URL":"https:\/\/doi.org\/10.1007\/s00236-011-0139-6","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8]]}}}