TITLE:
1-Way Multihead Quantum Finite State Automata
AUTHORS:
Debayan Ganguly, Kingshuk Chatterjee, Kumar Sankar Ray
KEYWORDS:
1-Way Quantum Finite State Automaton (1QFA), k-Letter Quantum Finite State Automata (k-Letter QFA), 1-Way Multihead Quantum Finite State Automaton (1QFA(k)), 1-Way Deterministic 2-Head Finite State Automaton (1DFA((2)), 1-Way Reversible Multihead Finite State Automaton (1RMFA(k))
JOURNAL NAME:
Applied Mathematics,
Vol.7 No.9,
May
31,
2016
ABSTRACT: 1-way multihead quantum finite state
automata (1QFA(k)) can be thought of modified version of 1-way quantum finite
state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA)
respectively. It has been shown by Moore and Crutchfield as well as Konadacs
and Watrous that 1QFA can’t accept all regular language. In this paper, we show
different language recognizing capabilities of our model 1-way multihead QFAs.
New results presented in this paper are the following ones: 1) We show that
newly introduced 1-way 2-head quantum finite state automaton (1QFA(2))
structure can accept all unary regular languages. 2) A language which can’t be
accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be
accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way
reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition
of language.