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. 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, and also show several separation results for blind/non-blind counter automata. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-319-22360-5_19 | CoRR |
Field | DocType | Volume |
Discrete mathematics,Quantum finite automata,Two-way deterministic finite automaton,Deterministic automaton,Nondeterministic finite automaton,Timed automaton,Pushdown automaton,Probabilistic automaton,Mathematics,Büchi automaton | Journal | abs/1412.6761 |
Citations | PageRank | References |
3 | 0.37 | 18 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masaki Nakanishi | 1 | 3 | 1.39 |
Abuzer Yakaryilmaz | 2 | 168 | 25.31 |