LOGCFLのある部分クラスについて
スポンサーリンク
概要
- 論文の詳細を見る
1-turn PDAでは受理できない言語でもLOG-space transducerによって変換してやると、1-turn PDAで受理できるようになるものが存在する。そのような言語のクラスをLOGLCFLと定義し、ここでは次の3つのことについて証明する: (1)metalinear CFLのクラス⊆LOGLCFL (2)DPDA(f(n))(f(n)-turn DPDAによって受理される言語のクラス)⊆DSPACE(f(n)log(n)) (3)finite-turn DPDAによって受理される言語のクラス⊆LOGLCFL.これらの結果はlog-spaceで決定性のTM上でのスタックの中身の扱い方を考えることによって求められる。
- 一般社団法人電子情報通信学会の論文
- 1998-03-24