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)∗b(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 k1k_{1}-letter QFA A1{\cal A}_1 and a k2k_{2}-letter QFA A2{\cal A}_2, over the same input alphabet ΣΣ are equivalent if and only if they are (n2mk−1−mk−1+k)(n^2m^{k-1}-m^{k-1}+k)-equivalent, where m=∣Σ∣m=|Σ| is the cardinality of ΣΣ, k=max⁡(k1,k2)k=\max(k_{1},k_{2}), and n=n1+n2n=n_{1}+n_{2}, with n1n_{1} and n2n_{2} being the numbers of states of A1{\cal A}_{1} and A2{\cal A}_{2}, respectively. When k=1k=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=1m=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 n^2m^{k-1}-m^{k-1}+k, then the worst time complexity is exponential, i.e., O(n6mn2mk−1−mk−1+2k−1)O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1}). Therefore, we design a polynomial-time O(m2k−1n8+kmkn6)O(m^{2k-1}n^{8}+km^kn^{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 kk is thought of as a constant.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.