Probabilistic rebound turing machines

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) pound [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 pound [PRTM(o(logn))], and (iii) there is a language accepted by a deterministic one-marker rebound automaton, but not in pound [PRTM(o(logn))], where pound [PRTM(o(logn))] denotes the class of languages recognized by o(logn) space-bounded PRTMs with error probability less than 1/2. Furthermore, we show that there is an infinite space hierarchy for pound [PRTM(o(logn))]. We finally show that pound [PRTM(o(logn))] is not closed under concatenation, Kleene+, and length-preserving homomorphism. This paper answers two open problems in a previous paper. (C) 2002 Elsevier Science B.V. All rights reserved.