Japanese | English

トップページへ戻る

詳細

   
フルテキストURLA030050000105.pdf ( 226.3KB ) 公開日 2010-04-19
タイトルConstant leaf-size hierarchy of three-dimensional alternating turing machines
作成者坂本, 眞人
井上, 克司
作成者ヨミサカモト, マコト
イノウエ, カツシ
作成者別表記Sakamoto, Makoto
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
本文言語eng
著者キーワードLeaf-size
alternation
apace complexity
three-dimensional Turing machine
three-dimensional finite automation
主題工学
資料タイプtext
ファイル形式application/pdf
出版者山口大学工学部
出版者ヨミヤマグチ ダイガク コウガクブ
NII資料タイプ紀要論文
ISSN1345-5583
NCIDAA11422756
学内刊行物(紀要等)山口大学工学部研究報告
掲載誌名山口大学工学部研究報告
掲載誌名別表記Memoirs of the Faculty of Engineering, Yamaguchi University
50
1
開始ページ31
終了ページ38
発行日1999-10
関連情報URL(IsPartOf)http://memoirs.lib-e.yamaguchi-u.ac.jp/
著者版/出版社版出版社版
リポジトリIDA030050000105
地域区分山口大学
URIhttp://www.lib.yamaguchi-u.ac.jp/yunoca/handle/A030050000105