Memoirs of the Faculty of Engineering, Yamaguchi University
Back to Top
Permalink : https://petit.lib.yamaguchi-u.ac.jp/15246
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 49 Issue 1
published_at 1998
線型以下の空間量をもつ2方向(インクドット)マルチカウンタオートマタの交代性
ALTERNATION FOR TWO-WAY (INKDOT) MULTI-COUNTER AUTOMATA WITH SUBLINEAR SPACE
Yoshinaga Tsunehiro
Xu Jianliang
Inoue Katsushi
About This Article
Descriptions
本論文では, 線型以下の空間量をもつ交代性マルチカウンタオートマタに関する交代の階層性, 及び線型以下の空間量をもつ2方向1インクドット交代性マルチカウンタオートマタに関する基本的ないくつかの性質について考察している。初めに, 線型以下の空間量に制限された交代性マルチカウンタオートマタは, 無限の交代階層性を有することを示す。次に, 線型以下の空間量の交代性マルチカウンタオートマタにおいて, 1インクドットをもつ場合とそうでない場合との受理能力の関係について考察する。例えば, 各l⊇1 (l⊇1 (l≠3))に対し, 任意の入力上の任意の計算路において, 全称状態(存在状態)から始まり, 高々l-1回の交代を行う2方向交代性マルチカウンタオートマタに関しては, 1インクドットをもつ場合の方が, もたない場合よりも真に受理能力が高いことなどを証明する。
Creator Keywords
alternating multi-counter automata
1-inkdot
alternation hierarchy
sublinear space
computational complexity
Other Article
PP. 49 - 56
PP. 57 - 64
PP. 121 - 127
PP. 129 - 136