2008/12/05 by Daowen Qiu, Qiu, Daowen, Xiangfu Zou +5
Computer Science · #Computational Complexity (cs.CC) #F.1.1 #F.1.2 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #cs.CC #cs.FL
paper · pdf · doi:10.48550/arxiv.0812.1061
18 pages; this is a further revised version
openalex publication_date 2008/12/05 · arxiv created 2010/10/24 · arxiv updated 2010/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Multi-letter \it quantum finite automata (QFAs) were a quantum variant of classical \it one-way multi-head finite automata (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages (a+b)*b that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a k1-letter QFA \cal A1 and a k2-letter QFA \cal A2, over the same input alphabet Σ are equivalent if and only if they are (n2mk-1-mk-1+k)-equivalent, where m=|Σ| is the cardinality of Σ, k=max(k1,k2), and n=n1+n2, with n1 and n2 being the numbers of states of \cal A1 and \cal A2, respectively. When k=1, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e., m=1). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than n2mk-1-mk-1+k, then the worst time complexity is exponential, i.e., O(n6m^n2mk-1-mk-1+2k-1). Therefore, we design a polynomial-time O(m2k-1n8+kmkn6) algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and k is thought of as a constant.