Alternating rebound Turing machines

This paper introduces an alternating rebound Turing machine and investigate s some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a determin istic (nondeterministic and alternating) rebound Turing machine, and URTM d enote an ARTM with only universal states. We first investigate a relationsh ip between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deter ministic rebound automaton, but not accepted by any o(log n) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound cou nter automata are more powerful than two-way deterministic counter automata . We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted b y alternating rebound automata, but not accepted by any o(log n) space-boun ded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log n. Furthermore, we inves tigate a relationship between the strong and weak modes of space complexity , and finally show that the classes of languages accepted by o(log n) space -bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kle ene +.