コンテンツメニュー

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

Memoirs of the Faculty of Engineering, Yamaguchi University Volume 50 Issue 1 Page 31-38
published_at 1999-10
A030050000105.pdf
[fulltext] 226 KB
Title
Constant leaf-size hierarchy of three-dimensional alternating turing machines
Creators Sakamoto Makoto
Creators Inoue Katsushi
Source Identifiers
Creator Keywords
Leaf-size alternation apace complexity three-dimensional Turing machine three-dimensional finite automation
‘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
Subjects
工学 ( Other)
Languages eng
Resource Type departmental bulletin paper
Publishers 山口大学工学部
Date Issued 1999-10
File Version Version of Record
Access Rights open access
Relations
[ISSN]1345-5583
[NCID]AA11422756
[isVersionOf] [URI]http://memoirs.lib-e.yamaguchi-u.ac.jp/
Schools 工学部