Masaki Nakanishi ; Abuzer Yakaryılmaz ; Aida Gainutdinova - New results on classical and quantum counter automata

dmtcs:1528 - Discrete Mathematics & Theoretical Computer Science, September 27, 2019, vol. 21 no. 4 -
New results on classical and quantum counter automataArticle

Authors: Masaki Nakanishi ; Abuzer Yakaryılmaz ; Aida Gainutdinova

    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. We also obtain new results on classical counter automata regarding language recognition. 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, and also show several separation results for blind/non-blind counter automata.

    Volume: vol. 21 no. 4
    Section: Automata, Logic and Semantics
    Published on: September 27, 2019
    Accepted on: September 3, 2019
    Submitted on: July 13, 2016
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computational Complexity,Quantum Physics

    Consultation statistics

    This page has been seen 1130 times.
    This article's PDF has been downloaded 235 times.