Two quantum finite automata are equivalent if for all input string
ω over the input alphabet the two automata accept
ω with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a
k1-letter QFA
A1 and a
k2-letter QFA
A2 over
Σ={σ}, are equivalent if and only if they are
(n1+n2)4+k−1-equivalent where
ni is the number of states of
Ai,
i=1,2, and
k=max{k1,k2}. In this letter, we improve the above upper-bound to
(n12+n22−1)+k. This also answers an open problem of Qiu et al. [Acta Informatica 48 (2011) 271-290]. Further, we show that, in the case of
Σ={σ1,...,σt} with
2≤t<∞, there exists an integer
z such that
A1 and
A2 are equivalent if and only if they satisfy
z-equivalent.
We first show that given a
k1-letter quantum finite automata
A1 and a
k2-letter quantum finite automata
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
n1,
i=1,2, are the numbers of state in
Ai respectively, and
k=max{k1,k2}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a
k1-letter measure many quantum finite automaton
A1 and a
k2-letter measure many quantum finite automaton
A2 are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the numbers of state in
Ai respectively, and
k=max{k1,k2}. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for
k-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether
L≥λ(A1)=L≥λ(A2) where
0<λ≤1 and
Ai are
ki-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for
k-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.
The relationships among various quantum automata are clarified, and in particular, variously equivalent characterizations of quantum automata are established. The G-quantum automata, g-quantum automata, (generalized) quantum automata, G-quantum grammars and g-quantum grammars are presented, and their connections to some of the other existing quantum automata are expounded. Under a certain condition, the equivalence between the G(g)-quantum automata and G(g)-quantum grammars is discussed. Therefore the problem of quantum grammars generating quantum regular languages is solved. The relation between quantum and regular languages is dealt with, and particularly, two open problems proposed by Gudder are answered. Finally, the method of decreasing the dimensions of spaces of states on quantum automata is given.
In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a
k1-letter quantum finite automaton
A1 and a
k2-letter quantum finite automaton
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a
k1-letter measure many quantum finite automaton
A1 and a
k2-letter measure many quantum finite automaton
A2 are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}.
Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a
k-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a
k-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a
k-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.