Constant leaf-size hierarchy of three-dimensional alternating turing machines

‘Leaf -size ’(or‘branching ’) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this pater, we investigate the effect of constant leaves of three-dimensional alternating Turing machines, and show the following facts : (1) For cubic input tapes, k leaf-and L(m) space-bounded three-dimensional alternating Turing machines with only universal states are equivalent to the same space-bounded three-dimensional deterministic Turing machines for any integer k ? 1 and any function L(m). (2) For cubic input tapes, k + 1 leaf-and o(lof m)space-bounded three-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k ? 1

Leaf-size

alternation

apace complexity

three-dimensional Turing machine

three-dimensional finite automation