caa a22 4500 445869666 CHVBK 20180317145507.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00236-011-0139-6 doi (NATIONALLICENCE)springer-10.1007/s00236-011-0139-6 Multi-letter quantum finite automata: decidability of the equivalence and minimization of states [Elektronische Daten] [Daowen Qiu, Lvzhou Li, Xiangfu Zou, Paulo Mateus, Jozef Gruska] Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovič, Acta Informatica 19:377-384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a+b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275-306, 2000) as well as Kondacs and Watrous (66-75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237:275-306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k 1-letter QFA $${{\mathcal A}_1}$$ and a k 2-letter QFA $${{\mathcal A}_2}$$ over the same input alphabet Σ, they are equivalent if and only if they are (n 2 m k-1−m k-1+k)-equivalent, where m =|Σ| is the cardinality of Σ, k =max(k 1,k 2), and n =n 1+n 2, with n 1 and n 2 being numbers of states of $${{\mathcal A}_{1}}$$ and $${{\mathcal A}_{2}}$$ , respectively. When k =1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275-306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m 2k-1 n 8+km k n 6) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237:275-306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE. Springer-Verlag, 2011 Qiu Daowen Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut Li Lvzhou Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut Zou Xiangfu Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut Mateus Paulo SQIG—Instituto de Telecomunicações, Departamento de Matemática, Instituto Superior Técnico, TULisbon, Av. Rovisco Pais, 1049-001, Lisbon, Portugal aut Gruska Jozef Faculty of Informatics, Masaryk University, Brno, Czech Republik aut Acta Informatica Springer-Verlag 48/5-6(2011-08-01), 271-290 0001-5903 48:5-6<271 2011 48 236 https://doi.org/10.1007/s00236-011-0139-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00236-011-0139-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Qiu Daowen Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut NATIONALLICENCE 700 1- Li Lvzhou Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut NATIONALLICENCE 700 1- Zou Xiangfu Department of Computer Science, Sun Yat-sen University, 510006, Guangzhou, China aut NATIONALLICENCE 700 1- Mateus Paulo SQIG—Instituto de Telecomunicações, Departamento de Matemática, Instituto Superior Técnico, TULisbon, Av. Rovisco Pais, 1049-001, Lisbon, Portugal aut NATIONALLICENCE 700 1- Gruska Jozef Faculty of Informatics, Masaryk University, Brno, Czech Republik aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 48/5-6(2011-08-01), 271-290 0001-5903 48:5-6<271 2011 48 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer