A Leaf-Size Hierarchy of Three-Dimensional Alternating Turing Machines
Makoto Sakamoto, Katsushi Inoue, A. S. Ito · Institutional Repositories DataBase (IRDB) · 1996
Alternating Turing machines were introduced as a generalization of nondeterministic Turing machines and as a mechanism to model parallel computation. ”Leaf-size” (or ”branching”) is the minimum number of leaves of some accepting computation trees of alternating Turing machines. Leaf-size, in a sense, reflects the minimum number of processors that run in parallel in accepting a given input. In this paper, we investigate a hierarchy of complexity classes based on leaf-size bounded computations for three-dimensional alternating Turing machines, and show that for any positive integer k＞__-1 and for any two functions L: N→N and L': N→N such that (1) L is a three-dimensionally space-constructible function such that L (m)^ ＜__- m (m＞__-