Two-way Quantum One-counter Automata

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
LaTeX2e, 14 pages, 3 figures

Keywords

Computational Complexity, Quantum Physics, F.1.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30833

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0110005
 http://arxiv.org/abs/cs/0110005

Collections

arXiv