A Leaf-Size Hierarchy of Alternating Rebound Turing Machines
Lan Zhang, Katsushi Inoue, Ito, Akira, Yue Wang · Universitätsbibliothek Gießen · 2002
This paper continues the investigation of the fundamental properties of alternating rebound Turing machines (ARTMs). In particular, we shall introduce a simple, natural complexity measure for ARTMs, called "leaf-size", and provide a hierarchy of complexity classes based on leaf-size bounded computations. Leaf-size, in a sense, reflects the number of processors which run in parallel in reading a given input. We show that for any positive integer $k \geq 1$ and for any two functions $L : N\to N\cup \{0\}$ and $L' : N \to N\cup\{0\}$ such that (i) $L$ is space constructible by a deterministic rebound Turing machine, (ii) $L(n)^{k+1} = o(\log n)$, and (iii) $L'(n) = o(L(n))$, there exists a language accepted by a strongly $L(n)$ space-bounded and $L(n)^k$ leaf-size bounded ARTM, but not accepted by any weakly $L(n)$ space-bounded and $L'(n)^k$ leaf-size bounded ARTM. We further show that for any positive integer $k \geq 1$,there exists a language accepted by a $2k+4$ leaf-size bounded alternating rebound automaton, but not accepted by any weakly $o(\log n)$ space-bounded and $k$ leaf-size bounded ARTM.