Name
Abstract | ||
|---|---|---|
This paper introduces a probabilistic rebound Turing machine (PRTM), and investigates the fundamental property of the machine. We first prove a sublogarithmic lower space bound on the space complexity of this model with bounded errors for recognizing specific languages. This lower bound strengthens a previous lower bound for conventional probabilistic Turing machines with bounded errors. We then show, by using our lower space bound and an idea in the proof of it, that i) [PRTM(o(logn))] is incomparable with the class of context-free languages, ii) there is a language accepted by a two-way deterministic one counter automaton, but not in [PRTM(o(logn))], and where [PRTM(o(logn))] denotes the class of languages recognized by o(logn) space-bounded PRTMs with error probability less than . Furthermore, we show that there is an infinite space hierarchy for [PRTM(o(logn))]. We finally show that [PRTM(o(logn))] is not closed under concatenation, Kleene +, and length-preserving homomorphism. This paper answers two open problems in a previous paper. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0304-3975(01)00098-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
infinite space hierarchy,lower space,conventional probabilistic,sublogarithmic lower space,counter automaton,context-free language,previous paper,bounded error,space complexity,probabilistic rebound | Journal | 270 |
Issue | ISSN | Citations |
1-2 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 7 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lan Zhang | 1 | 6 | 1.53 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 4 | 0.93 |
| Yue Wang | 4 | 34 | 9.08 |