Decidability of the Equivalence of Multi-Letter Quantum Finite Automata

Abstract

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{)}^{\ast }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 $k_1$-letter QFA ${\mathcal{A}}_1$ and a $k_2$-letter QFA ${\mathcal{A}}_2$, over the same input alphabet $\Sigma$ are equivalent if and only if they are $(n^2{m}^{k-1}-m^{k-1}+k)$-equivalent, where $m=|\Sigma |$ is the cardinality of $\Sigma$, $k=\max (k_1,k_2)$, and $n=n_1+n_2$, with $n_1$ and $n_2$ being the numbers of states of ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$, 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 $n^2{m}^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e., $O(n^6{m}^{n^2{m}^{k-1}-m^{k-1}+2k-1})$. Therefore, we design a polynomial-time $O(m^{2k-1}{n}^8+k{m}^k{n}^6)$ 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.

arXiv comment18 pages; this is a further revised version

Cited by in corpus (3)

• On hybrid models of quantum finite automata
• Exponentially more concise quantum recognition of non-RMM regular languages
• Characterizations of one-way general quantum finite automata