Classical and Quantum Counter Automata on Promise Problems
Classical and Quantum Counter Automata on Promise Problems
复制标题
DOI：
10.1007/978-3-319-22360-5_19
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
M. Nakanishi;A. Yakaryılmaz
中科院分区：
文献类型：
--
作者：
M. Nakanishi;A. Yakaryılmaz
在本文中，我们证明了零错误的单向量子单计数器自动机在承诺问题上比概率对应的自动机更强大。然后，我们在拉斯维加斯单向概率单计数器自动机和单向确定性单计数器自动机之间获得了类似的分离结果。最后，推测单向概率单盲计数器自动机无法识别等式语言的克林闭包 [A. Yakaryilmaz：单向实时量子机的优越性。 RAIRO - 理论。信息。和应用。 46（4）：615–641（2012）]。我们证明这个猜想是错误的。
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.