Unary probabilistic and quantum automata on promise problems |
| |
Authors: | Aida Gainutdinova Abuzer Yakary?lmaz |
| |
Affiliation: | 1.Department of Theoretical Cybernetics, Institute of Computational Mathematics and Information Technologies,Kazan Federal University,Kazan,Russia;2.Center for Quantum Computer Science,University of Latvia,Rīga,Latvia |
| |
Abstract: | We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error unary QFAs are more powerful than bounded-error unary PFAs, and, contrary to the binary language case, the computational power of Las-Vegas QFAs and bounded-error PFAs is equivalent to the computational power of deterministic finite automata (DFAs). Then, we present a new family of unary promise problems defined with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|