Physics – Quantum Physics
Scientific paper
2011-04-19
Int J Theor Phys (2011) 50: 1262-1281
Physics
Quantum Physics
25 pages
Scientific paper
10.1007/s10773-010-0582-0
{\it Two-way finite automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous, and {\it two-way two-tape deterministic finite automata} (2TFA) were introduced by Rabin and Scott. In this paper we study 2TFA and propose a new computing model called {\it two-way two-tape finite automata with quantum and classical states} (2TQCFA). First, we give efficient 2TFA algorithms for recognizing languages which can be recognized by 2QCFA. Second, we give efficient 2TQCFA algorithms to recognize several languages whose status vis-a-vis 2QCFA have been posed as open questions, such as $L_{square}=\{a^{n}b^{n^{2}}\mid n\in \mathbf{N}\}$. Third, we show that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by {\it $(k+1)$-tape deterministic finite automata} ($(k+1)$TFA). Finally, we introduce {\it $k$-tape automata with quantum and classical states} ($k$TQCFA) and prove that $\{a^{n}b^{n^{k}}\mid n\in \mathbf{N}\}$ can be recognized by $k$TQCFA.
Li Lvzhou
Qiu Daowen
Zheng Shenggen
No associations
LandOfFree
Two-tape finite automata with quantum and classical states 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 Two-tape finite automata with quantum and classical states, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-tape finite automata with quantum and classical states will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-182278