Two-Tape Finite Automata with Quantum and Classical States

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and 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 two-way two-tape finite automata with quantum and classical states (2TQCFA). First, we give efficient 2TFA algorithms for identifying 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ⁿbⁿ² | n ? N}L_{mathit{square}}={a^{n}b^{n^{2}}mid nin mathbf{N}}. Third, we show that {aⁿb^nk | n ? N}{a^{n}b^{n^{k}}mid nin mathbf{N}} can be recognized by (k+1)-tape deterministic finite automata ((k+1)TFA). Finally, we introduce k-tape automata with quantum and classical states (kTQCFA) and prove that {aⁿb^nk | n ? N}{a^{n}b^{n^{k}}mid nin mathbf{N}} can be recognized by kTQCFA.