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) £[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 (iii) there is a language accepted by a deterministic one-marker rebound automaton, but not in £[PRTM(o(logn))], where £[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 £[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.

Authors

• Lan Zhang University of Science and Technology of China
• Katsushi Inoue
• Akira Ito
• Yue Wang University of Central Florida

Keywords

• Probabilistic rebound Turing machine
• Rebound automaton
• Space hierarchy
• Closure property