Computer Science – Computational Complexity
Scientific paper
2011-06-26
Computer Science
Computational Complexity
Corollary 3 is deleted, since it is folk. Comments are welcome
Scientific paper
Two quantum finite automata are equivalent if for all input string $\omega$ over the input alphabet the two automata accept $\omega$ with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a $k_1$-letter QFA $\mathcal{A}_1$ and a $k_2$-letter QFA $\mathcal{A}_2$ over $\Sigma=\{\sigma\}$, are equivalent if and only if they are $(n_1+n_2)^4+k-1$-equivalent where $n_i$ is the number of states of $\mathcal{A}_i$, $i=1,2$, and $k=\max\{k_1,k_2\}$. In this letter, we improve the above upper-bound to $(n_1^2+n_2^2-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 $\Sigma=\{\sigma_1,...,\sigma_t\}$ with $2\leq t<\infty$, there exists an integer $z$ such that $\mathcal{A}_1$ and $\mathcal{A}_2$ are equivalent if and only if they satisfy $z$-equivalent.
No associations
LandOfFree
Some results on equivalence of multi-letter quantum finite automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Some results on equivalence of multi-letter quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some results on equivalence of multi-letter quantum finite automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-585992