A leaf-size hierarchy of three-dimensional alternating turing Machines

Creators Sakamoto Makoto

Creators Inoue Katsushi

Creators Ito Akira

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)^<k+1>＜__- m (m＞__-

[ISSN]0386-3433

[NCID]AA0086073X