pith. sign in

arxiv: 1607.00811 · v1 · pith:C5R2HIOEnew · submitted 2016-07-04 · 💻 cs.FL

2-tape 1-way Quantum Finite State Automata

classification 💻 cs.FL
keywords finitequantumstateautomatontapeautomatat1qfaaccepted
0
0 comments X
read the original abstract

1-way quantum finite state automata are reversible in nature, which greatly reduces its accepting property. In fact, the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. We introduce 2-tape 1-way quantum finite state automaton (2T1QFA(2))which is a modified version of 1-way 2-head quantum finite state automaton(1QFA(2)). In this paper, we replace the single tape of 1-way 2-head quantum finite state automaton with two tapes. The content of the second tape is determined using a relation defined on input alphabet. The main claims of this paper are as follows: (1)We establish that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept all regular languages (2)A language which cannot be accepted by any multi-head deterministic finite automaton can be accepted by 2-tape 1-way quantum finite state automaton(2T1QFA(2)) .(3) Exploiting the superposition property of quantum automata we show that 2-tape 1-way quantum finite state automaton(2T1QFA(2)) can accept the language L=ww.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.