全称状態のみを持つ対数以下空間限定1ペブル交代性チューリング機械

概要

論文の詳細を見る
任意の空間関数L(n)に対し、全称状態だけをもつL(n)空間限定1ペブル交代性チューリング機械で受理される言語族をびSPACE^<peb>(L(n))と記す。本論文では、log log n ≦ L(n) ≦ log nであるようなL(n)に対し、びSPACE^<peb>(L(n))の2,3の性質について考察する.まず、log log n ≦ L(n) = o(log n)であるような任意のL(n)に対し、びSPACE^<peb>(L(n))は、2方向決定性1カウンタオートマタで受理される言語族と比較不能であることを示す。次に、log log n ≦ L(n) = of log n)であるような任意の£？に対し、1og log n 空間限定交代性1gブルチューリング機械では受理されるが、ひSPACE^<peb>(L(n))には含まれないような言語が存在することを示す。最後に、空間階層性について考察し、任意の1ペブル空間構成可能な関数£？≦1og n と任意の関数L^1(n) = o(L(n))に対し、びSPACE^<peb>(L(n))には含まれるがび夕PACE^<peb>(L^1(n))には含まれないような言語が存在することを示す。
社団法人電子情報通信学会の論文
2004-05-13