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
- 山口大学工学部の論文
山口大学工学部 | 論文
- 対話式ヒューマンインターフェイスを備えた食事支援用ロボットハンドの開発
- 強度異方性を考慮した三郡変成岩風化土の斜面安定解析
- 不連続面に起因した斜面崩壊とそのせん断強度
- 三郡変成岩風化土の土工上の問題とその改良
- サンドコンパクションパイルの打設が砂杭周辺地盤の強度特性に及ぼす影響