Nakanishi, Masaki and Yakaryılmaz, Abuzer and Gainutdinova, Aida - 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 automata

Authors: Nakanishi, Masaki and Yakaryılmaz, Abuzer and Gainutdinova, Aida

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.


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


Share