Name
Abstract | ||
|---|---|---|
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 oneway 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. |
Year | Venue | Keywords |
|---|---|---|
2019 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | quantum automata,counter automata,promise problems,blind counter,zero-error,Las-Vegas algorithms |
Field | DocType | Volume |
Discrete mathematics,Quantum,Kleene star,Automaton,Language recognition,Probabilistic logic,Conjecture,Mathematics | Journal | 21.0 |
Issue | ISSN | Citations |
4.0 | 1462-7264 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Masaki Nakanishi | 1 | 131 | 21.62 |
| Abuzer Yakaryilmaz | 2 | 168 | 25.31 |
| Aida Gainutdinova | 3 | 59 | 4.95 |