Hierarchy and equivalence of multi-letter quantum finite automata

Multi-letter quantum finite automata (QFAs) are a new one-way QFA model proposed recently by Belovs, Rosmanis, and Smotrovs [A. Belovs, A. Rosmanis, J. Smotrovs, Multi-letter reversible and quantum finite automata, in: Proceedings of the 13th International Conference on Developments in Language Theory, DLT’2007, Harrachov, Czech Republic, in: Lecture Notes in Computer Science, vol. 4588, Springer, Berlin, 2007, pp. 60–71], and they showed that multi-letter QFAs can accept with no error some regular languages ((a+b)∗b) that are unacceptable by the one-way QFAs. In this paper, we continue to study multi-letter QFAs. We mainly focus on two issues: (1) we show that (k+1)-letter QFAs are computationally more powerful than k-letter QFAs, that is, (k+1)-letter QFAs can accept some regular languages that are unacceptable by any k-letter QFA. A comparison with the one-way QFAs is made by some examples; (2) we prove that a k1-letter QFA A1 and another k2-letter QFA A2 are equivalent, if and only if, they are (n1+n2)4+k−1-equivalent, and the time complexity of determining the equivalence of two multi-letter QFAs using this method is O(n12+k2n4+kn8), where n1 and n2 are the numbers of states of A1 and A2, respectively, and k=max(k1,k2). Some other issues are addressed for further consideration.