Two-way Quantum One-counter Automata

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.

• Publication year

  2001

• Venue

  arXiv.org

• Publication date

  2001-01-19

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv cs/0110005
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quantum versus Probabilistic One-Way Finite Automata with Counter

  2001cited by this paper
• Exact results for accepting probabilities of quantum automata

  2001cited by this paper
• On the Class of Languages Recognizable by 1-Way Quantum Finite Automata

  2000cited by this paper
• Quantum Finite State Transducers

  2000cited by this paper
• Quantum Pushdown Automata

  2000cited by this paper
• One-way probabilistic reversible and quantum one-counter automata

  2000cited by this paper
• On the Lower Bounds for One-Way Quantum Automata

  2000cited by this paper
• Optimal lower bounds for quantum automata and random access codes

  1999cited by this paper
• Characterizations of 1-Way Quantum Finite Automata

  1999cited by this paper
• Two-way finite automata with quantum and classical state

  1999cited by this paper
• Quantum Finite Multitape Automata

  1999cited by this paper
• Quantum Finite One-Counter Automata

  1999cited by this paper
• Probabilities to Accept Languages by Quantum Finite Automata

  1999cited by this paper
• Undecidability on quantum finite automata

  1999cited by this paper
• 1-way quantum finite automata: strengths, weaknesses and generalizations

  1998cited by this paper
• Reversible space equals deterministic space

  1997cited by this paper
• Quantum automata and quantum grammars

  1997cited by this paper
• On the power of quantum finite state automata

  1997influential reference
• Quantum theory, the Church–Turing principle and the universal quantum computer

  1985cited by this paper
• Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines

  1961cited by this paper
• "PROOF"

  1934cited by this paper

• Computing power of Turing machines in the framework of unsharp quantum logic

  2015cites this paper
• The computing power of Turing machine based on quantum logic

  2012cites this paper
• An Analysis of Absorbing Times of Quantum Walks

  2002cites this paper
• Performance evaluation of mobile agent on its living time and target existing rates in servers

  2002cites this paper