$ CFL subseteq NSPACE(o(log ^ 2(n)))$?

$ CFL $は文脈自由な言語のクラスです。

質問

     

$ CFL $は$ o(log ^ {2}(n))$非決定論的空間で解くことができるのですか? $ DCFL
$はどうですか?

ベストアンサー

はい。以下の論文の定理4です。

フィリップ・ルイス2世、リチャード・エドウイン・スターンズ、ユリス・ハートマニス:
文脈自由な文脈依存言語の認識のためのメモリ境界。 SWCT(FOCS)1965:191-202。

編集:私は申し訳ありません。私の答えは役に立たない。私は “小さいo”を逃した。愚か…
私は何をすべきか分かりません。回答を削除しますか?

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です