Hierarchy and equivalence of multi-letter quantum finite automata

Details Hierarchy and equivalence of multi-letter quantum finite automata Hierarchy and equivalence of multi-letter quantum finite automata

2008-12-04

arxiv.org/abs/0812.0852v3

Theoretical Computer Science, 410 (30-32) (2009) 3006-3017.

Computer Science

Computational Complexity

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

Scientific paper

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)^{*}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 ${\cal A}_1$ and another $k_{2}$-letter QFA ${\cal 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}+kn^{8})$, where $n_{1}$ and $n_{2}$ are the numbers of states of ${\cal A}_{1}$ and ${\cal A}_{2}$, respectively, and $k=\max(k_{1},k_{2})$. Some other issues are addressed for further consideration.

Affiliated with

Also associated with

No associations

Rating

Hierarchy and 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 Hierarchy and 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 Hierarchy and equivalence of multi-letter quantum finite automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-135544