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

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

Creators Sakamoto Makoto

Creators Inoue Katsushi

‘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

[ISSN]1345-5583

[NCID]AA11422756

[isVersionOf] [URI]http://memoirs.lib-e.yamaguchi-u.ac.jp/