Japanese | English

トップページへ戻る

詳細

   
フルテキストURLKJ00004351187.pdf ( 863.0KB ) 公開日 2010-04-19
タイトルA leaf-size hierarchy of three-dimensional alternating turing Machines
作成者Sakamoto, Makoto
Inoue, Katsushi
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>__-;1), (2) lim_<m→∞>L(m)L'(m)^k/log m=0 and (3) lim_<m→∞>L'(m)/L(m)=0, L(m) space bounded and L(m)^k leaf-size bounded three-dimensional alternating Turing machines are more powerful than L (m) space bounded and L'(m)^k leaf-size bounded three-dimensional alternating Turing machines. We let the input tapes, throughout this paper, be restricted to cubic ones.
本文言語eng
主題工学
資料タイプtext
ファイル形式application/pdf
出版者山口大学工学部
出版者ヨミヤマグチ ダイガク コウガクブ
NII資料タイプ紀要論文
ISSN0386-3433
NCIDAA0086073X
学内刊行物(紀要等)Technology reports of the Yamaguchi University
掲載誌名Technology reports of the Yamaguchi University
5
5
開始ページ367
終了ページ382
発行日1996-12
著者版/出版社版出版社版
備考本文データは国立情報学研究所において電子化したものである
リポジトリIDKJ00004351187
地域区分山口大学
URIhttp://www.lib.yamaguchi-u.ac.jp/yunoca/handle/KJ00004351187