Japanese | English

トップページへ戻る

詳細

   
フルテキストURLKJ00000157152.pdf ( 1.1MB ) 公開日 2010-04-19
タイトルALTERNATION FOR TWO-WAY (INKDOT) MULTI-COUNTER AUTOMATA WITH SUBLINEAR SPACE
タイトルヨミセンガタ イカ ノ クウカンリョウ オ モツ 2ホウコウ インクドット マルチカウンタ オートマタ ノ コウタイセイ
タイトル別表記線型以下の空間量をもつ2方向(インクドット)マルチカウンタオートマタの交代性
作成者Yoshinaga, Tsunehiro
Xu, Jianliang
Inoue, Katsushi
作成者ヨミヨシナガ, ツネヒロ
イノウエ, カツシ
作成者別表記井上, 克司
作成者所属山口大学工学部
内容記述(抄録等)本論文では, 線型以下の空間量をもつ交代性マルチカウンタオートマタに関する交代の階層性, 及び線型以下の空間量をもつ2方向1インクドット交代性マルチカウンタオートマタに関する基本的ないくつかの性質について考察している。初めに, 線型以下の空間量に制限された交代性マルチカウンタオートマタは, 無限の交代階層性を有することを示す。次に, 線型以下の空間量の交代性マルチカウンタオートマタにおいて, 1インクドットをもつ場合とそうでない場合との受理能力の関係について考察する。例えば, 各l⊇1 (l⊇1 (l≠3))に対し, 任意の入力上の任意の計算路において, 全称状態(存在状態)から始まり, 高々l-1回の交代を行う2方向交代性マルチカウンタオートマタに関しては, 1インクドットをもつ場合の方が, もたない場合よりも真に受理能力が高いことなどを証明する。
本文言語eng
著者キーワードalternating multi-counter automata
1-inkdot
alternation hierarchy
sublinear space
computational complexity
主題情報学
資料タイプtext
ファイル形式application/pdf
出版者山口大学工学部
出版者ヨミヤマグチ ダイガク コウガクブ
NII資料タイプ紀要論文
ISSN0372-7661
NCIDAN00244228
学内刊行物(紀要等)山口大学工学部研究報告
掲載誌名山口大学工学部研究報告
掲載誌名別表記Memoirs of the Faculty of Engineering, Yamaguchi University
49
1
開始ページ101
終了ページ111
発行日1998
著者版/出版社版出版社版
備考本文データは国立情報学研究所において電子化したものである
リポジトリIDKJ00000157152
地域区分山口大学
URIhttp://www.lib.yamaguchi-u.ac.jp/yunoca/handle/KJ00000157152