線型以下の空間量をもつ2方向(インクドット)マルチカウンタオートマタの交代性
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 49 Issue 1
Page 101-111
published_at 1998
Title
ALTERNATION FOR TWO-WAY (INKDOT) MULTI-COUNTER AUTOMATA WITH SUBLINEAR SPACE
線型以下の空間量をもつ2方向(インクドット)マルチカウンタオートマタの交代性
Creators
Yoshinaga Tsunehiro
Creators
Xu Jianliang
Creators
Inoue Katsushi
Source Identifiers
Creator Keywords
alternating multi-counter automata
1-inkdot
alternation hierarchy
sublinear space
computational complexity
本論文では, 線型以下の空間量をもつ交代性マルチカウンタオートマタに関する交代の階層性, 及び線型以下の空間量をもつ2方向1インクドット交代性マルチカウンタオートマタに関する基本的ないくつかの性質について考察している。初めに, 線型以下の空間量に制限された交代性マルチカウンタオートマタは, 無限の交代階層性を有することを示す。次に, 線型以下の空間量の交代性マルチカウンタオートマタにおいて, 1インクドットをもつ場合とそうでない場合との受理能力の関係について考察する。例えば, 各l⊇1 (l⊇1 (l≠3))に対し, 任意の入力上の任意の計算路において, 全称状態(存在状態)から始まり, 高々l-1回の交代を行う2方向交代性マルチカウンタオートマタに関しては, 1インクドットをもつ場合の方が, もたない場合よりも真に受理能力が高いことなどを証明する。
Languages
eng
Resource Type
departmental bulletin paper
Publishers
山口大学工学部
Date Issued
1998
File Version
Version of Record
Access Rights
open access
Relations
[ISSN]0372-7661
[NCID]AN00244228
Schools
工学部