Two-tape finite automata with quantum and classical states

Details Two-tape finite automata with quantum and classical states Two-tape finite automata with quantum and classical states

2011-04-19

arxiv.org/abs/1104.3634v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182278