1-Way Multihead Quantum Finite State Automata
- 1 Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, India
- 2 Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, India
- 3 Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, India
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.
- Moore, C. and Crutchfield, J. (1997) Quantum Automata and Quantum Grammars. Theoretical Computer Science, 237, 275-306. http://dx.doi.org/10.1016/S0304-3975(98)00191-1
- Kondacs, A. and Watrous, J. (1997) On the Power of Quantum Finite State Automata. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami, 66-75. http://dx.doi.org/10.1109/SFCS.1997.646094
- Ambainis, A. and Freivalds, R. (1998) One-Way Quantum Finite Automata: Strengths, Weakness and Generalizations. IEEE 39th Annual Symposium on Foundations of Computer Science, 332-342. http://dx.doi.org/10.1109/SFCS.1998.743469
- Ambainis, A., Bonner, R.F., Freivalds, R. and Kikusts, A. (1999) Probabilities to Accept Languages by Quantum Finite Automata. COCOON, 174-183. http://dx.doi.org/10.1007/3-540-48686-0_17
- Ambainis, A., Bcandry, M., Golovkins, M., Kikusts, A., Mercer, M. and Therien, D. (2004) Algebric Results on Quantum Automata. STACS, 93-104.
- Bertoni, A., Mereghetti, C. and Palano, B. (2003) Quantum Computing: 1 way Quantum Automata. Developments Language Theory, 1-20.
- Ambainis, A. and Watrous, J. (2002) Two Way Finite Automata with Quantum and Classical States. Theoretical Computer Science, 287, 299-311.
- Ambainis, A., Beaudry, M., Golovkins, M., Kikusts, A., Mercer, M. and Therien, D. (2004) Algebraic Results on Quantum Automata. In: Diekert, V. and Habib, M., Eds., STACS, LNCS, Vol. 2996, Springer, Heidelberg, 93-104.
- Dzelme, I. (2003) Kvantu Automar Jauktajiem Stavokliem. Technical Report, University of Latvia.
- Nayak, A. (1999) OPtimal Lower Bounds for Quantum Automata and Random Access Codes. Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 369-377. http://dx.doi.org/10.1109/sffcs.1999.814608
- Rabin, M.O. and Scott, D. (1964) Finite Automata and Their Decision Problems. Sequential Machines, Selected Papers, Addition-Wesley, 63-91.
- Rosenberg, A.L. (1966) On Multihead Finite Automata. IBM Journal of Research and Development, 10, 388-394. http://dx.doi.org/10.1147/rd.105.0388
- Kutrib, M. and Malchar, A. (2013) One-Way Reversible Multi-Head Finite Automata. Reversible Computation, Lecture Notes in Computer Science, 7581, 14-28. http://dx.doi.org/10.1007/978-3-642-36315-3_2
- Morita, K. (2011) Two-Way Reversible Multi-Head Finite Automata. Fundamenta Informaticae, IOS Press, 241-254.