Two-way Quantum One-counter Automata

Simple item page
dc.creatorYamasaki, Tomohiro
dc.creatorKobayashi, Hirotada
dc.creatorImai, Hiroshi
dc.date2001-10-02
dc.date.accessioned2026-07-07T03:17:44Z
dc.date.available2026-07-07T03:17:44Z
dc.descriptionAfter 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.
dc.descriptionLaTeX2e, 14 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/cs/0110005
dc.identifierhttp://arxiv.org/abs/cs/0110005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30833
dc.subjectComputational Complexity
dc.subjectQuantum Physics
dc.subjectF.1.1
dc.titleTwo-way Quantum One-counter Automata
dc.typetext

Files

Collections

arXiv