@inproceedings{c216e5e9e0d94df89740b987411ff3ad,
title = "Classical and quantum counter automata on promise problems",
abstract = "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.",
keywords = "Blind counter, Counter automata, Exact probabilistic and quantum computation, Promise problems, Quantum automata",
author = "Masaki Nakanishi and Abuzer Yakaryılmaz",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 20th International Conference on Implementation and Application of Automata, CIAA 2015 ; Conference date: 18-08-2015 Through 21-08-2015",
year = "2015",
doi = "10.1007/978-3-319-22360-5\_19",
language = "English",
isbn = "9783319223599",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "224--237",
editor = "Frank Drewes",
booktitle = "Implementation and Application of Automata - 20th International Conference, CIAA 2015, Proceedings",
address = "Germany",
}