Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s11128-017-1799-0 | Quantum Information Processing |
Keywords | Field | DocType |
Quantum finite automata,Unary promise problems,Bounded-error,Las-Vegas algorithms,Succinctness | Quantum finite automata,Discrete mathematics,Unary language,Unary operation,Succinctness,Deterministic finite automaton,Computer science,Markov chain,Probabilistic logic,Binary number | Journal |
Volume | Issue | ISSN |
17 | 2 | 1570-0755 |
Citations | PageRank | References |
3 | 0.38 | 29 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aida Gainutdinova | 1 | 59 | 4.95 |
| Abuzer Yakaryilmaz | 2 | 168 | 25.31 |