「LOGCFL」の版間の差分

提供: miniwiki
移動先:案内検索
ja>Addbot
(ボット: 言語間リンク 3 件をウィキデータ上の d:q448600 に転記)
 
(1版 をインポートしました)
 
(相違点なし)

2018/8/19/ (日) 17:31時点における最新版

計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。

NLAC1の間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。

外部リンク