Hierarchy and equivalence of multi-letter quantum finite automata

Abstract

Multi-letter {\it quantum finite automata} (QFAs) were a new one-way QFA model proposed recently by Belovs, Rosmanis, and Smotrovs (LNCS, 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{)}^{\ast }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 $k_1$-letter QFA ${\mathcal{A}}_1$ and another $k_2$-letter QFA ${\mathcal{A}}_2$ are equivalent if and only if they are $(n_1+n_2{)}^4+k-1$-equivalent, and the time complexity of determining the equivalence of two multi-letter QFAs using this method is $O(n^{12}+k^2{n}^4+k{n}^8)$, where $n_1$ and $n_2$ are the numbers of states of ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$, respectively, and $k=\max (k_1,k_2)$. Some other issues are addressed for further consideration.

22 pages, 8 figures. The is a further revised version, and it has been accepted for publication in Theoretical Computer Science