対数以下の空間量を持つ交代プッシュダウンオートマタに関するいくつかの考察

概要

論文の詳細を見る
まず、対数以下の空間量をもつ交代プッシュダウンオートマタ (APDAs) におけるalternation-depthとalternation-sizeの関係について考察し、alternation-depthが2に制限されたloglog n空間限定APDAによっては受理されるが、lim_<n→∞>[a(n).logn/n^<1/2>]=0を満たすどんな関数a(n)に対しても、o(log n) 空間限定でa(n)alternation-size限定の交代チューリング機械によっては受理されない言語が存在することを示す。次に、対数以下の空間量をもつインクドットAPDAsにおけるinkdot-depthとinkdot-sizeの関係について考察し、inkdot-depthが1に制限されたloglog n空間限定APDAによっては受理されるが、lim_<n→∞>[d(n).logn/n^<1/2>]=0を満たすどんな関数d(n)に対しても、o(log n)空間限定でd(n)inkdot-size限定の交代チューリング機械によっては受理されない言語が存在することを示す。最後に、対数以下の空間量をもつ交代プッシュダウンオートマタにおける空間階層性が無限であることを示す。
社団法人電子情報通信学会の論文
1996-11-22