%0 Journal Article
%T Classical and quantum counter automata on promise problems
%A Masaki Nakanishi
%A Abuzer Yakary£¿lmaz
%J Computer Science
%D 2014
%I arXiv
%X In this paper, we show that one-way quantum one-counter automaton with zero-error is more powerful than its probabilistic counterpart on promise problems. Then, we obtain a similar separation result between Las Vegas one-way probabilistic one-counter automaton and one-way deterministic one-counter automaton. Lastly, it was conjectured that one-way probabilistic one blind-counter automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz: Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false.
%U http://arxiv.org/abs/1412.6761v1