Computer Science – Computational Complexity
Scientific paper
2001-10-02
Computer Science
Computational Complexity
LaTeX2e, 14 pages, 3 figures
Scientific paper
After the first treatments of quantum finite state automata by Moore and Crutchfield and by Kondacs and Watrous, a number of papers study the power of quantum finite state automata and their variants. This paper introduces a model of two-way quantum one-counter automata (2Q1CAs), combining the model of two-way quantum finite state automata (2QFAs) by Kondacs and Watrous and the model of one-way quantum one-counter automata (1Q1CAs) by Kravtsev. We give the definition of 2Q1CAs with well-formedness conditions. It is proved that 2Q1CAs are at least as powerful as classical two-way deterministic one-counter automata (2D1CAs), that is, every language L recognizable by 2D1CAs is recognized by 2Q1CAs with no error. It is also shown that several non-context-free languages including {a^n b^{n^2}} and {a^n b^{2^n}} are recognizable by 2Q1CAs with bounded error.
Imai Hiroshi
Kobayashi Hirotada
Yamasaki Tomohiro
No associations
LandOfFree
Two-way Quantum One-counter Automata 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-way Quantum One-counter Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-way Quantum One-counter Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-60407